Research

I’ve done research on various topics, especially during my past studies. Below are papers that I’ve coauthored.

Adopting Trusted Types in Production Web Frameworks to Prevent DOM-Based Cross-Site Scripting: A Case Study

Google Research: pub50513
Authors: Pei Wang, Bjarki Ágúst Guðmundsson, Krzysztof Kotowicz

Cross-site scripting (XSS) is a common security vulnerability found in web applications. DOM-based XSS, one of the variants, is becoming particularly more prevalent with the boom of single-page applications where most of the UI changes are achieved by modifying the DOM through inbrowser scripting. It is very easy for developers to introduce XSS vulnerabilities into web applications since there are many ways for user-controlled, unsanitized input to flow into a Web API and get interpreted as HTML markup and JavaScript code.

An emerging Web API proposal called Trusted Types aims to prevent DOM XSS by making Web APIs secure by default. Different from other XSS mitigations that mostly focus on post-development protection, Trusted Types direct developers to write XSS-free code in the first place.

A common concern when adopting a new security mechanism is how much effort is required to refactor existing code bases. In this paper, we report a case study on adopting Trusted Types in a well-established web framework. Our experience can help the web community better understand the benefits of making web applications compatible with Trusted Types, while also getting to know the related challenges and resolutions. We focused our work on Angular, which is one of the most popular web development frameworks available on the market.

Presented at the 2021 Workshop on Designing Security for the Web, co-located with the 6th IEEE European Symposium on Security and Privacy, 2021 by Pei Wang

Counting pop-stacked permutations in polynomial time

arXiv: 1908.08910
doi: doi:10.1080/10586458.2021.1926001
Authors: Anders Claesson, Bjarki Ágúst Guðmundsson, Jay Pantone

Permutations in the image of the pop-stack operator are said to be pop-stacked. We give a polynomial-time algorithm to count pop-stacked permutations up to a fixed length and we use it to compute the first 1000 terms of the corresponding counting sequence. Only the first 16 terms had previously been computed. With the 1000 terms we prove some negative results concerning the nature of the generating function for pop-stacked permutations. We also predict the asymptotic behavior of the counting sequence using differential approximation.

Published in Experimental Mathematics, 2021, Pages 1-8

Enumerating permutations sortable by k passes through a pop-stack

arXiv: 1710.04978
doi: doi:10.1016/j.aam.2019.04.002
Authors: Anders Claesson, Bjarki Ágúst Guðmundsson

In an exercise in the first volume of his famous series of books, Knuth considered sorting permutations by passing them through a stack. He noted that, out of the n! permutations on n elements, C_n of them can be sorted by a single pass through a stack, where C_n is the n-th Catalan number. Many variations of this exercise have since been considered, including allowing multiple passes through the stack and using different data structures. West classified the permutations that are sortable by 2 passes through a stack, and a formula for the enumeration was later proved by Zeilberger. The permutations sortable by 3 passes through a stack, however, have yet to be enumerated. We consider a variation of this exercise using pop-stacks. For any fixed k, we give an algorithm to derive a generating function for the permutations sortable by k passes through a pop-stack. Recently the generating function for k=2 was given by Pudwell and Smith (the case k=1 being trivial). Running our algorithm on a computer cluster we derive the generating functions for k at most 6. We also show that, for any k, the generating function is rational.

See source code at GitHub.

Presented at Math Colloquium, University of Iceland, Iceland, September 2017 by Bjarki Ágúst Guðmundsson (PDF, Announcement)
Presented at Stærðfræði á Íslandi, Iceland, October 2017 by Bjarki Ágúst Guðmundsson (PDF)
Poster at Permutation Patterns, Dartmouth College, USA, 2018 by Anders Claesson
Presented at Algebraic Combinatorics Online Workshop, 2020 by Anders Claesson (Video)
Referenced on OEIS
Published in Advances in Applied Mathematics, Volume 108, 2019, Pages 79-96

Formalizing the translation method in Agda

hdl: 1946/28736
Authors: Bjarki Ágúst Guðmundsson (MSc thesis)

If P and Q are sets of combinatorial objects, the translation method, introduced by Wood and Zeilberger (2009), allows one to turn an algebraic proof of the identity |P| = |Q| into a bijection between P and Q. We give a formalized implementation of the translation method in the programming language Agda. In contrast to the implementation previously given by Wood and Zeilberger, the bijections produced by our implementation are formally verified, making our implementation more robust. We also take advantage of the fact that Agda is a proof assistant, allowing users of our implementation to use the existing facilities provided by Agda for developing proofs. In particular, converting an existing algebraic proof for use in our implementation is often straightforward.

We prove that the expressions used in our implementation form a commutative semiring. Based on this we implement a semiring solver, allowing one to apply the translation method automatically to certain identities. We also show how cancellation procedures, introduced by Feldman and Propp (1995), can be used to give meaning to subtraction, division and k-th roots in the translation method, and we implement the cancellation procedure that represents subtraction. Finally we give a philosophical discussion about the inner workings of the translation method, and use that to count the number of “natural” bijections for an identity considered by Wood and Zeilberger.

See source code at GitHub.

Defended at Reykjavík University, Iceland, June 2017 by Bjarki Ágúst Guðmundsson (PDF)

Automatic discovery of structural rules of permutation classes

arXiv: 1705.04109
Authors: M. Albert, C. Bean, A. Claesson, B. Gudmundsson, and H. Ulfarsson

We introduce an algorithm that conjectures the structure of a permutation class in the form of a disjoint cover of “rules”; similar to generalized grid classes. The cover is usually easily verified by a human and translated into an enumeration. The algorithm is successful on different inputs than other algorithms and can succeed with any polynomial permutation class. We apply it to every non-polynomial permutation class avoiding a set of length four patterns. The structures found by the algorithm can sometimes allow an enumeration of the permutation class with respect to permutation statistics, as well as choosing a permutation uniformly at random from the permutation class. We sketch a new algorithm formalizing the human verification of the conjectured covers.

See source code at GitHub.

Presented at ICE-TCS Seminar, Reykjavik University, Iceland, November 2014 by Christian Bean
Presented at Experimental Mathematics Seminar, Rutgers University, USA, March 2015 by Henning Ulfarsson (Video: Part 1, Part 2)
Presented at Scottish Combinatorics Meeting, University of Glasgow, Scotland, April 2016 by Christian Bean (PDF)
Presented at Permutation Patterns, Howard University, USA, June 2016 by Christian Bean (Abstract, pg. 10)
Referenced on OEIS
Published in Mathematics of Computation, Volume 88, Number 318, July 2019, Pages 1967–1990

Algorithmic coincidence classification of mesh patterns

Authors: Bjarki Ágúst Guðmundsson, Tómas Ken Magnússon, Henning Ulfarsson See source code at GitHub.

Will be Tómas’ MSc thesis subject.

Presented at Permutation Patterns, Howard University, USA, June 2016 by Bjarki Ágúst Guðmundsson (PDF)
Poster at Permutation Patterns, Reykjavík University, Iceland, June 2017 by Tómas Ken Magnússon (PDF)

Bounds and Fixed-Parameter Algorithms for Weighted Improper Coloring

arXiv: 1509.00099
doi: doi:10.1016/j.entcs.2016.03.013
Authors: Bjarki Ágúst Guðmundsson, Tómas Ken Magnússon, Björn Orri Sæmundsson

We study the weighted improper coloring problem, a generalization of defective coloring. We present some hardness results and in particular we show that weighted improper coloring is not fixed-parameter tractable when parameterized by pathwidth. We generalize bounds for defective coloring to weighted improper coloring and give a bound for weighted improper coloring in terms of the sum of edge weights. Finally we give fixed-parameter algorithms for weighted improper coloring both when parameterized by treewidth and maximum degree and when parameterized by treewidth and precision of edge weights. In particular, we obtain a linear-time algorithm for weighted improper coloring of interval graphs of bounded degree.

Published in Electronic Notes in Theoretical Computer Science, Volume 322, 18 April 2016, Pages 181-195
Presented at ICTCS 2015, the 16th Italian Conference on Theoretical Computer Science by Tómas Ken Magnússon
Presented at ICE-TCS Seminar, Reykjavik University, Iceland, 2015 by Tómas Ken Magnússon

Collatz meets Fibonacci

arXiv: 1404.3054
doi: doi:10.1080/0025570X.2022.2023307
Authors: Michael Albert, Bjarki Gudmundsson, Henning Ulfarsson

The Collatz map is defined for a positive even integer as half that integer, and for a positive odd integer as that integer threefold, plus one. The Collatz conjecture states that when the map is iterated the number one is eventually reached. We study permutations that arise as sequences from this iteration. We show that permutations of this type of length up to 14 are enumerated by the Fibonacci numbers. Beyond that excess permutations appear. We will explain the appearance of these excess permutations and give an upper bound on the exact enumeration.

Presented at Stærðfræði á Íslandi, Iceland, 2013 by Bjarki Ágúst Guðmundsson (PDF)
Presented at MIT Combinatorics Seminar, Boston, MA, October 2013 by Henning Ulfarsson (PDF)
Poster at Permutation Patterns, East Tennessee State University, USA, July 2014 by Michael Albert (PDF)
Presented at the 2015 Joint Mathematics Meetings, San Antonio, TX by Michael Albert
Referenced on OEIS
Published in The MAA Mathematics Magazine, Volume 95, 18 Februar 2022 - Issue 2, Pages 130-136