Joan Boyar

I&C Journal 2026 Journal Article

On the online weighted non-crossing matching problem

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

We introduce and study the weighted version of an online matching problem in the Euclidean plane with non-crossing constraints: points with non-negative weights arrive online, and an algorithm can match an arriving point to one of the unmatched previously arrived points. In the classic model, the decision on how to match (if at all) a newly arriving point is irrevocable. The goal is to maximize the total weight of matched points under the constraint that straight-line segments corresponding to the edges of the matching do not intersect. The unweighted version of the problem was introduced in the offline setting by Atallah in 1985, and this problem became a subject of study in the online setting with and without advice in several recent papers. We observe that deterministic online algorithms cannot guarantee a non-trivial competitive ratio for the weighted problem, but we give upper and lower bounds on the problem with bounded weights. In contrast to the deterministic case, we show that using randomization, a constant competitive ratio is possible for arbitrary weights. We also study other variants of the problem, including revocability and collinear points, both of which permit non-trivial online algorithms, and we give upper and lower bounds for the attainable competitive ratios. Finally, we prove an advice complexity bound for obtaining optimality, improving the best known bound.

TCS Journal 2024 Journal Article

Advice complexity of adaptive priority algorithms

• Joan Boyar
• Kim S. Larsen
• Denis Pankratov

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 was developed for proving lower bounds on the amount of advice required to achieve certain approximation ratios in this rather powerful model. To capture most of the algorithms that are considered greedy-like, the even stronger model of adaptive priority algorithms is needed. We extend the adaptive priority model to include advice. We modify the reduction-based framework from the fixed priority case to work with the more powerful adaptive priority algorithms, simplifying the proof of correctness and strengthening all previous lower bounds by a factor of two in the process. As evidence that adding advice to adaptive priority algorithms extends both adaptive priority algorithms and online algorithms with advice, we present a purely combinatorial adaptive priority algorithm with advice for Minimum Vertex Cover on triangle-free graphs of maximum degree three. Our algorithm achieves optimality and uses at most 7 n / 22 bits of advice. No adaptive priority algorithm without advice can achieve optimality without advice, and we prove that an online algorithm with advice needs more than 7 n / 22 bits of advice to reach optimality. We show connections between exact algorithms and priority algorithms with advice. The branching in branch-and-reduce algorithms can be seen as trying all possible advice strings, and all priority algorithms with advice that achieve optimality define corresponding exact algorithms, priority exact algorithms. Lower bounds on advice-based adaptive algorithms imply lower bounds on running times of exact algorithms designed in this way.

MFCS Conference 2023 Conference Paper

Online Algorithms with Predictions (Invited Talk)

• Joan Boyar

We give an introduction to online algorithms with predictions, from an algorithms researcher’s perspective, concentrating on minimization problems.

ICML Conference 2023 Conference Paper

Paging with Succinct Predictions

• Antonios Antoniadis 0001
• Joan Boyar
• Marek Eliás 0001
• Lene M. Favrholdt
• Ruben Hoeksma
• Kim S. Larsen
• Adam Polak 0001
• Bertrand Simon 0001

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. Previous work on learning-augmented paging has investigated predictions on (i) when the current page will be requested again (reoccurrence predictions), (ii) the current state of the cache in an optimal algorithm (state predictions), (iii) all requests until the current page gets requested again, and (iv) the relative order in which pages are requested. We study learning-augmented paging from the new perspective of requiring the least possible amount of predicted information. More specifically, the predictions obtained alongside each page request are limited to one bit only. We develop algorithms satisfy all three desirable properties of learning-augmented algorithms – that is, they are consistent, robust and smooth – despite being limited to a one-bit prediction per request. We also present lower bounds establishing that our algorithms are essentially best possible.

TCS Journal 2018 Journal Article

Multiplicative complexity of vector valued Boolean functions

• Joan Boyar
• Magnus Gausdal Find

We consider the multiplicative complexity of Boolean functions with multiple bits of output, studying how large a multiplicative complexity is necessary and sufficient to provide a desired nonlinearity. For so-called ΣΠΣ circuits, we show that there is a tight connection between error correcting codes and circuits computing functions with high nonlinearity. Combining this with known coding theory results, we show that functions with n inputs and n outputs with the highest possible nonlinearity must have at least 2. 32n AND gates. We further show that one cannot prove stronger lower bounds by only appealing to the nonlinearity of a function; we show a bilinear circuit computing a function with almost optimal nonlinearity with the number of AND gates being exactly the length of such a shortest code. Additionally we provide a function which, for general circuits, has multiplicative complexity at least 2 n − 3. Finally we study the multiplicative complexity of “almost all” functions. We show that every function with n bits of input and m bits of output can be computed using at most 2. 5 ( 1 + o ( 1 ) ) m 2 n AND gates.

I&C Journal 2017 Journal Article

On the list update problem with advice

• Joan Boyar
• Shahin Kamali
• Kim S. Larsen
• Alejandro López-Ortiz

We study the online list update problem under the advice model of computation. Under this model, an online algorithm receives partial information about the unknown parts of the input in the form of some bits of advice generated by a benevolent offline oracle. We show that advice of linear size is required and sufficient for a deterministic algorithm to achieve an optimal solution or even a competitive ratio better than 15/14. On the other hand, we show that surprisingly two bits of advice are sufficient to break the lower bound of 2 on the competitive ratio of deterministic online algorithms and achieve a deterministic algorithm with a competitive ratio of 1. 6 ¯. In this upper-bound argument, the bits of advice determine the algorithm with smaller cost among three classical online algorithms, Timestamp and two members of the Mtf2 family of algorithms. We also show that Mtf2 algorithms are 2. 5-competitive.

TCS Journal 2015 Journal Article

Cancellation-free circuits in unbounded and bounded depth

• Joan Boyar
• Magnus Gausdal Find

We study the notion of “cancellation-free” circuits. This is a restriction of XOR circuits, but can be considered as being equivalent to previously studied models of computation. The notion was coined by Boyar and Peralta in a study of heuristics for a particular circuit minimization problem. They asked how large a gap there can be between the smallest cancellation-free circuit and the smallest XOR circuit. We present a new proof showing that the difference can be a factor Ω ( n / log 2 ⁡ n ). Furthermore, our proof holds for circuits of constant depth. We also study the complexity of computing the Sierpinski matrix using cancellation-free circuits and give a tight Ω ( n log ⁡ ( n ) ) lower bound.

TCS Journal 2015 Journal Article

Relative interval analysis of paging algorithms on access graphs

• Joan Boyar
• Sushmita Gupta
• Kim S. Larsen

Access graphs, which have been used previously in connection to competitive analysis and relative worst order analysis to model locality of reference in paging, are considered in connection with relative interval analysis. The algorithms LRU, FIFO, FWF, and FAR are compared using the path, star, and cycle access graphs. In this model, some of the results obtained are not surprising. However, although LRU is found to be strictly better than FIFO on paths, it has worse performance on stars, cycles, and complete graphs, in this model. We solve an open question from Dorrigiv et al. (2009) [13], obtaining tight bounds on the relationship between LRU and FIFO with relative interval analysis.

TCS Journal 2014 Journal Article

A comparison of performance measures via online search

• Joan Boyar
• Kim S. Larsen
• Abyayananda Maiti

Since the introduction of competitive analysis, a number of alternative measures for the quality of online algorithms have been proposed, but, with a few exceptions, these have generally been applied only to the online problem for which they were developed. Recently, a systematic study of performance measures for online algorithms was initiated [J. Boyar, S. Irani, K. S. Larsen, A comparison of performance measures for online algorithms, in: Eleventh International Algorithms and Data Structures Symposium, in: Lecture Notes in Computer Science, vol. 5664, Springer, 2009, pp. 119–130], first focusing on a simple server problem. We continue this work by studying a fundamentally different online problem, online search, and the Reservation Price Policies in particular. The purpose of this line of work is to learn more about the applicability of various performance measures in different situations and the properties that the different measures emphasize. We investigate the following analysis techniques: Competitive, Relative Worst Order, Bijective, Average, Relative Interval, Random Order, and Max/Max. In addition, we have established the first optimality proof for Relative Interval Analysis.

TCS Journal 2010 Journal Article

Priority algorithms for graph optimization problems

• Allan Borodin
• Joan Boyar
• Kim S. Larsen
• Nazanin Mirmohammadi

We continue the study of priority or “greedy-like” algorithms as initiated in Borodin et al. (2003) [10] and as extended to graph theoretic problems in Davis and Impagliazzo (2009) [12]. Graph theoretic problems pose some modeling problems that did not exist in the original applications of Borodin et al. and Angelopoulos and Borodin (2002) [3]. Following the work of Davis and Impagliazzo, we further clarify these concepts. In the graph theoretic setting, there are several natural input formulations for a given problem and we show that priority algorithm bounds in general depend on the input formulation. We study a variety of graph problems in the context of arbitrary and restricted priority models corresponding to known “greedy algorithms”.

TCS Journal 2010 Journal Article

Tight results for Next Fit and Worst Fit with resource augmentation

• Joan Boyar
• Leah Epstein
• Asaf Levin

It is well known that the two simple algorithms for the classic bin packing problem, NF and WF both have an approximation ratio of 2. However, WF seems to be a more reasonable algorithm, since it never opens a new bin if an existing bin can still be used. Using resource augmented analysis, where the output of an approximation algorithm, which can use bins of size b > 1, is compared to an optimal packing into bins of size 1, we give a complete analysis of the asymptotic approximation ratio of WF and of NF, and use it to show that WF is strictly better than NF for any 1 < b < 2, while they have the same asymptotic performance guarantee for all b ≥ 2, and for b = 1.

MFCS Conference 2008 Conference Paper

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

• Joan Boyar
• Philip Matthews
• René Peralta 0001

Abstract We study the complexity of the Shortest Linear Program (SLP) problem, which is to minimize the number of linear operations necessary to compute a set of linear forms. SLP is shown to be NP-hard. Furthermore, a special case of the corresponding decision problem is shown to be Max SNP-Complete. Algorithms producing cancellation-free straight-line programs, those in which there is never any cancellation of variables in GF(2), have been proposed for circuit minimization for various cryptographic applications. We show that such algorithms have approximation ratios of at least 3/2 and therefore cannot be expected to yield optimal solutions to non-trivial inputs.

TCS Journal 2008 Journal Article

Tight bounds for the multiplicative complexity of symmetric functions

• Joan Boyar
• René Peralta

The multiplicative complexity of a Boolean function f is defined as the minimum number of binary conjunction (AND) gates required to construct a circuit representing f, when only exclusive-or, conjunction and negation gates may be used. This article explores in detail the multiplicative complexity of symmetric Boolean functions. New techniques that allow such exploration are introduced. They are powerful enough to give exact multiplicative complexities for several classes of symmetric functions. In particular, the multiplicative complexity of computing the Hamming weight of n bits is shown to be exactly n − H N ( n ), where H N ( n ) is the Hamming weight of the binary representation of n. We also show a close relationship between the complexities of basic symmetric functions and the fractal known as Sierpinski’s gasket.

MFCS Conference 2006 Conference Paper

Concrete Multiplicative Complexity of Symmetric Functions

• Joan Boyar
• René Peralta 0001

Abstract The multiplicative complexity of a Boolean function f is defined as the minimum number of binary conjunction (AND) gates required to construct a circuit representing f, when only exclusive-or, conjunction and negation gates may be used. This article explores in detail the multiplicative complexity of symmetric Boolean functions. New techniques that allow such exploration are introduced. They are powerful enough to give exact multiplicative complexities for several classes of symmetric functions. In particular, the multiplicative complexity of computing the Hamming weight of n bits is shown to be exactly n − H ℕ ( n ), where H ℕ ( n ) is the Hamming weight of the binary representation of n. We also show a close relationship between the complexity of symmetric functions and fractals derived from the parity of binomial coefficients.

TCS Journal 2006 Journal Article

The maximum resource bin packing problem

• Joan Boyar
• Leah Epstein
• Lene M. Favrholdt
• Jens S. Kohrt
• Kim S. Larsen
• Morten M. Pedersen
• Sanne Wøhlk

Usually, for bin packing problems, we try to minimize the number of bins used or in the case of the dual bin packing problem, maximize the number or total size of accepted items. This paper presents results for the opposite problems, where we would like to maximize the number of bins used or minimize the number or total size of accepted items. We consider off-line and on-line variants of the problems. For the off-line variant, we require that there be an ordering of the bins, so that no item in a later bin fits in an earlier bin. We find the approximation ratios of two natural approximation algorithms, First-Fit-Increasing and First-Fit-Decreasing for the maximum resource variant of classical bin packing. For the on-line variant, we define maximum resource variants of classical and dual bin packing. For dual bin packing, no on-line algorithm is competitive. For classical bin packing, we find the competitive ratio of various natural algorithms. We study the general versions of the problems as well as the parameterized versions where there is an upper bound of 1 k on the item sizes, for some integer k.

SODA Conference 2005 Conference Paper

The relative worst order ratio applied to paging

• Joan Boyar
• Lene M. Favrholdt
• Kim S. Larsen

TCS Journal 2000 Journal Article

On the multiplicative complexity of Boolean functions over the basis (∧,⊕,1)

• Joan Boyar
• René Peralta
• Denis Pochuev

The multiplicative complexity c∧(f) of a Boolean function f is the minimum number of AND gates in a circuit representing f which employs only AND, XOR and NOT gates. A constructive upper bound, c∧(f)=2(n/2)+1−n/2−2, for any Boolean function f on n variables (n even) is given. A counting argument gives a lower bound of c∧(f)=2(n/2)−O(n). Thus we have shown a separation, by an exponential factor, between worst-case Boolean complexity (which is known to be Θ(2nn−1 )) and worst-case multiplicative complexity. A construction of circuits for symmetric Boolean functions on n variables, requiring less than n+3 n AND gates, is described.

TCS Journal 1992 Journal Article

An arithmetic model of computation equivalent to threshold circuits

• Joan Boyar
• Gudmund Frandsen
• Carl Sturtivant

We define a new structured and general model of computation: circuits using arbitrary fan-in arithmetic gates over the characteristic-two finite fields (F 2n ). These circuits have only one input and one output. We show how they correspond naturally to boolean computations with n inputs and n outputs. We show that if circuit sizes are polynomially related, then the arithmetic circuit depth and the threshold circuit depth to compute a given function differ by at most a constant factor. We use threshold functions with arbitrary weights; however, we show that when compared to the usual threshold model, the depth measure of this generalised model differs only by at most a constant factor (at polynomial size). The fan-in of our arithmetic model is also unbounded in the most generous sense: circuit size is measured as the number of Σ and Π-gates; there is no bound on the number of “wires”. We show that these results are provable for any reasonable correspondence between strings of n-bits and elements of F 2n. And we find two such distinct characterizations. Thus, we show that arbitrary fan-in arithmetic computations over F 2n constitute a precise abstraction of Boolean threshold computations with the pleasant property that various algebraic laws have been recovered.

FOCS Conference 1991 Conference Paper

Subquadratic Zero-Knowledge

• Joan Boyar
• Gilles Brassard
• René Peralta 0001

The communication complexity of zero-knowledge proof systems is improved. Let C be a Boolean circuit of size n. Previous zero-knowledge proof systems for the satisfiability of C require the use of Omega (kn) bit commitments in order to achieve a probability of undetected cheating not greater than 2/sup -k/. In the case k=n, the communication complexity of these protocols is therefore Omega (n/sup 2/) bit commitments. A zero-knowledge proof is given for achieving the same goal with only O(n/sup m/+k square root n/sup m/) bit commitments, where m=1+ epsilon /sub n/ and epsilon /sub n/ goes to zero as n goes to infinity. In the case k=n, this is O(n square root n/sup m/). Moreover, only O(k) commitments need ever be opened, which is interesting if committing to a bit is significantly less expensive than opening a commitment. >

FOCS Conference 1982 Conference Paper

Inferring a Sequence Generated by a Linear Congruence

• Joan Boyar

Suppose it is known that {X 0, X 1, .. ., X n } is produced by a pseudo-random number generator of the form X i+1 = aX i + b mod m, but a, b, and m are unknown. Can one efficiently predict the remainder of the sequence with knowledge of only a few elements from that sequence? This question is answered in the affirmative and an algorithm is given.