Matrix multiplication with the standard algorithm has an algebraic complexity of O(n^3) for n x n matrices, but in 1969 Strassen found another algorithm for multiplying 2 x 2 matrices with which he showed that matrix multiplication can be done with a complexity of O(n^2.81) by applying his algorithm recursively for large matrices. We present a historical overview of the best known bounds on the matrix multiplication exponent, with the current best known bound of 2.371866 and methods, used to find new algorithms for other matrix multiplications, such as alternating least squares (ALS) and SAT solving. After this we present a novel method with which we found a rank 23 decomposition of the <3,3,3> matrix multiplication tensor that may be inequivalent to known decompositions. We also found decompositions for <2,2,2>, <2,2,3>, <2,2,4>, <2,3,3> and <2,2,5> that provide the same bounds as earlier found decompositions. Our method found many decompositions for the smaller tensors but only one for the larger due to time limits. The method is based on the alternating least squares method (ALS) with the modification that we 'push' the coefficients towards integer (or rational) numbers. After a number of iterations and rounding the result this sometimes yields exact decompositions so that we can bound the matrix multiplication exponent.

A set of lines passing through the origin in Euclidean space is called equiangular if the angle between any two lines is the same. The question of finding the maximum number of such lines, N(d) in any dimension d is an extensively studied problem. Closely related, is the problem of finding the maximum number of lines, N_α(d), such that the common angle between the lines is arccosα. In recent years, many progress has been made on this problem. We review some of these breakthrough results and the techniques they use to approach this problem. The first main result is a linear upper bound on N_α(d) which is found using a completely novel approach with respect to techniques used in previous works. Another main result that we discuss solves the problem of finding N_α(d) for high enough dimensions. Some classic results from some of the first studies on equiangular lines are also discussed. Finally, some suggestions are given for possible further research.

The increasing popularity of e-commerce has led to a greater emphasis on improving parcel delivery processes. Among the various stages of the delivery process, packing parcels into delivery vans affects the delivery time. The efficiency of delivery is optimized when each parcel is conveniently accessible upon arrival, thereby minimizing the requirement for additional repacking time. Therefore, streamlining parcel packing within delivery vehicles is a crucial aspect of improving overall delivery times in e-commerce. This thesis focuses on developing a packing solution that conforms to the the Last-In-First-Out (LIFO) principle, which is defined as ensuring that a parcel can be accessed by the delivery driver as soon as they reach the destination of the parcel. This is described as the 3D-Bin Packing Problem with Loading Constraints (3L-BPP). To solve this problem, a formulation of a Mixed Integer Linear Program (MILP) has been developed. To improve the speed and accuracy of the solution, a novel placement heuristic has been created. This heuristic is derived from the established Distance to the Front-Top-Right Corner (DFTRC)-2 method and is designed to generate an initial solution.

Both the MILP and the heuristic are tested on a data set of 789 distinct rides, provided by a Dutch postal company. The results demonstrate that (a modified version of) the heuristic successfully generated an initial solution for all rides in the dataset, with 98.9% being found within 3 seconds, and for the remaining 1.1%, the inclusion of a Genetic Algorithm led to a solution being found within 90 seconds. By using the heuristic to establish an initial solution that is then refined through optimization techniques for the MILP, the findings indicate that this approach yields the best outcomes in minimizing the number of incorrectly positioned parcels.

A code C is defined to be a set of S words, where a word is a sequence of n entries. We call S the size and n the length of the code. The entries of the code can have k different values, {0, .., (k − 1)}. Define a perfect k-hash code (PHC) as a code with the property that any collection of v words in the code is different at at least one index. PHC’s are useful mathematical objects within different fields of theoretical computer science and coding theory. This thesis will focus on one typical kind of PHC, a trifferent code. Such a trifferent code is defined as a PHC where k = v = 3. This means that any collection of three words in the code has to differ at some index. We now define T (n) to be the largest possible size of a trifferent code given that it has length n. The question that arises is, what is the value of T (n)? It turns out that determining the exact value is complicated, unless n is really small. Therefore, we try to understand the asymptotic nature of the function T (n). This is what we call the trifference problem. This paper will cover and prove the best known asymptotic upper and lower bound on T (n). Moreover, it will explain and include a Python code that can be used to show and prove all values of T (n) for n ∈ {1, .., 6}. Lastly, two different ways to explicitly construct trifferent codes for any value of n will be given and compared.

This thesis focuses on a problem formulated by Claude Shannon named the Shannon capacity. This problem is about information rate per time unit over a noisy channel. The noisy channel is here represented by a graph. We specifically focus on a class of circulant graphs that are denoted by C(n,k) with vertex set z/nz, where all vertices are connected with the k-1 vertices before and after it. We will discuss upper bounds that were found for the Shannon capacity and how C(n,k) behaves with these upper bounds. After that we will focus on multiple ways to calculate lower bounds for the Shannon capacity of $C(n,k)$. For these three search methods will be used. These are exhaustive searching for optimal values, optimal ways to make packagings and solutions created by using a special form. As last the answers will be discussed by combining the upper and lower bounds for C(n,k). From this conclusions are drawn after which some possibilities will be given for further research. 

Representation theory is a branch in mathematics that studies group homomorphisms between a group and the automorphism group of a vector space. A special representation that every group has is the regular representation. This representation permutes all elements of the group in a vector space which dimension is equal to the order of the group.
Within this vector space there are group invariant subspaces. There are several methods to finding representation invariant subspaces of this vector space.

This thesis aims to do two things: First of all, this thesis aims to give the reader an introduction to representation theory, presenting various key concepts, definitions and theorems. Moreover, ways to construct character tables are presented along with multiple worked out examples. Second, the regular representations of D4 and Q8 are decomposed into representation invariant subspaces of C8. To this end, two methods were used.

The first method (A), proposed by dr. Jeroen Spandaw, works out all the possible decompositions of the vector space a regular representation acts on. This is quite a laborious process in which change of basis matrices, expressed in several parameters, will have to be made for all generators of the considered group. The second methods (B), proposed by dr. Paul Visser, is known as the grand orthogonalization method and makes use of an extended version of the character table of the considered group.

Both methods are perfectly fine to make a desired decomposition. However, method A
takes a lot more computational effort than method B to come up with the desired result. The benefit of using method A over method B is that method A considers all possible decompositions, whereas method B only considers one of the infinitely many that are possible.

In 1961 Kasteleyn solved the dimer problem. With the use of Pfaffans he managed to find a formula to enumerate the number of perfect matchings on a lattice graph. In this thesis we take another look at the methods Kasteleyn used. Besides that, we proof that for an m × n lattice graph on the torus, where m and n are even, there does not exist a Pfaffan orientation. Instead, we prove that for an m × 2 and 2 × n lattice graph on the torus, where m and n are even, there does exist a Pfaffan orientation. For the m × n lattice graph on the torus, where m is even and n odd we present an orientation together with an algorithm with which we can simplify cycles. With this algorithm we prove that our orientation is Pfaffan. We will now describe the Pfaffan orientation. All horizontal edges are aimed to the right, all vertical edges switch between all going down for the first column, then up for the second column and so on. The edges that are on the border all have orientation opposite of the ongoing orientation.

Decision-tree evaluation is a widely-used classification approach known for its simplicity and effectiveness. Decision-tree models are shown to be helpful in classifying instances of fraud, malware, or diseases and can be used to make dynamic, flexible access decisions within an access-control system. These applications often require sensitive data of more than one party, like financial or health-related records. It is important to keep this data private, especially when the decision-tree evaluation is done in a collaborative manner where more than one party provides sensitive input data. Current privacy-preserving solutions only consider scenarios in which input data originates from a single source. However, collaboration for decision-tree evaluation tasks is needed more and more since these collaborations often bear fruit. Therefore, in this work we address Private Decision-Tree Evaluation in a collaborative setting. We assume one entity, called the server, that holds the decision tree and multiple users that provide private data on which the decision tree is evaluated. The focus of our research lies on solutions that make use of homomorphic encryption. We give ten different protocols that each take place in a different setting; either the holder of the decision tree receives the evaluation result or the users that provide the input. The protocols use Multi-Key Fully Homomorphic Encryption (FHE) or normal FHE with a Semi-Trusted Third Party (STTP). Additionally, we introduce a novel key-switching method within two of the STTP protocols such that the dependency on the STTP is greatly reduced. All protocols are proven to be secure in the semi-honest model and compared in terms of run-time complexity and communication costs. Due to the high computational overhead for the Multi-Key FHE schemes, the protocols that make use of these schemes are not yet feasible. Therefore, the protocols that use an STTP are the most promising. All protocols take no more than 4 communication rounds. Assuming that the implementation can be parallelized and given an input bit length of 4, the decision-tree evaluation in our protocols takes in the worst case between 60 and 160 hours, executed on an Intel Core Processor at 2.4 GHz with 16 GB memory.

This thesis investigates two types of classical capacities of both classical and quantum channels, giving rise to four different settings. The first type of classical capacity investigated is the ordinary capacity of a channel to transmit classical information with a probability of error which becomes arbitrarily small as the channel is used arbitrarily many times. The second type of classical capacity investigated is the capacity of a channel to transmit information with zero probability of error, called the zero-error classical capacity. The first setting which is studied is the ordinary capacity of a classical channel. The noisy channel coding theorem is proven in two different ways: one using the Markov inequality and the Law of Large Numbers and one using typical sets. The additivity of this capacity is also discussed. The second setting is the zero-error capacity of classical channel. Lower and upper bounds on this capacity are proven, and its superadditivity is discussed. The third setting is the ordinary classical capacity of a quantum channel. The Holevo-Schumacher-Westmoreland theorem is proven using typical subspaces and the packing lemma, and the superadditivity of the Holevo information is discussed in terms of entanglement at the encoder. The fourth and last setting investigated is that of the zero-error classical capacity of a quantum channel. It is shown that this capacity can be achieved using only pure input states and that this capacity never exceeds the ordinary classical capacity. Moreover, a detailed investigation of superactivation of the zero-error classical capacity is presented. A topic for further research would be an exposition of the analogous concepts in the case of the quantum capacity of quantum channels. Another topic for further research would be an explicit construction of two quantum channels whose zero-error classical capacity is superactivated.

This thesis deals with n-to-1 entanglement distillation protocols for bipartite quantum systems in a group theoretical setting. The local operations in the protocols are restricted to Clifford operations. An efficient representation of the elements of the Clifford group in terms of binary matrices is presented. Moreover, a characterization of the subgroup of the Clifford group which leaves the fidelity and the success probability invariant is given. Based on this characterization, a novel approach for the optimization of distillation protocols is presented: instead of checking every element of the Clifford group individually, it is sufficient to consider one element of every right coset of this subgroup. These new insights are used to find optimal protocols for n = 2, 3, 4 and 5.

Bell inequalities are certain probabilistic inequalities that should hold in the context of quantum measurement under assumption of a local hidden variable model. These inequalities can be violated according to the theory of quantum mechanics and have also been violated experimentally. Bell inequalities were therefore historically used to disprove local hidden variable models as an interpretation of quantum mechanics. An interesting question is to what degree Bell inequalities can be violated according to the theory of quantum mechanics. The degree to which a particular Bell inequality can be violated is quantified by the largest violation of the Bell inequality. A central question we address in this thesis is how large the largest violation can become when considering all possible Bell inequalities. In particular the CHSH-inequality, a well-known Bell inequality, has a largest violation equal to the square root of 2 and we want to find a Bell inequality with largest violation exceeding the square root of 2. This thesis consists of two main parts. In the first part we formally define Bell inequalities and the largest violation and prove several theorems about Bell inequalities. In the second part we search for Bell inequalities with largest violation exceeding the square root of 2. We do this by first approximating the largest violation of a given Bell inequality using numerical optimization. Next, using this approximation, we use numerical optimization to maximize the largest violation. Due to run-time restrictions we were only able to consider Bell inequalities with a relatively small number of terms and were unable to find any among them with largest violation exceeding the square root of 2.

Logistics service providers (LSPs) offering container transport to the hinterland of the Netherlands face the challenge of efficiently using the capacity of the barge in order to minimize cost, while part of the relevant information is still lacking at the moment decisions have to be made. The existing infrastructure and the transportation activities are studied and modeled as an online optimization problem with simultaneously vehicle routing and container-to-mode assignment. A characteristic of great importance in the problem is the uncertainty element that reflects in the requested appointment times that have to be confirmed by another agent in the network. An online optimization approach is proposed, where the input data come in sequentially and decisions have to be made in between, because new information becomes available only after the decision has been made. At each decision moment, the uncertainty element is converted to an offline optimization problem by disregarding the uncertainty or by simulating various potential future scenarios. Subsequently, the problem is modeled as a multi-commodity network design problem on a time-space graph. Four different solution methods are developed in order to solve the online optimization problem. Three confirmation based methods concern a model in which the uncertainty element is partially disregarded, by assuming that each requested appointment time will be scheduled at a specific time relative to the requested one. Alternatively, a much more complex method is developed in which various future scenarios are simulated for the requested appointment times given their probability vector. The simulation based model seeks robust solutions that are resistant to change, i.e., feasible and (sub)optimal for every potential future scenario that has been simulated. Using randomly generated (but realistic) instances, the computational results show that the proposed simulation model surpasses the simpler models both in terms of outcomes, robustness and reliability. However, the practical relevance is somewhat restricted in the sense that the model is built on several assumptions.

There are several ways to write the number 5 as a sum of positive integers, disregarding order. A quick calculation shows that this can be done in 7 ways: 5 = 5, 5 = 4 + 1, 5 = 3 + 2, 5 = 3 + 1 + 1, 5 = 2 + 2 + 1, 5 = 2 + 1 + 1 + 1 and 5 = 1 + 1 + 1 + 1 + 1. In the same way, we can count the number of ways for each integer n. Although this calculation is trivial, a closed form for this function is not as easily obtained as one for combinations, for example. This work formulates and proves Rademacher's formula for these partition numbers. It also tries to uncover some key ideas behind the proof, the supporting theory and other inspirations.

In intermodal transport multiple types of vehicles are used to transport containers. If the routes of the vehicles are known, then the container allocation can be optimized. This problem can be modelled as an integral multi-commodity min cost flow problem on a time-space graph. This model has an arc-based and path-based form. In this thesis, the path-based form is derived from the arc-based form. Some of the methods that can be used to solve this model are column generation, Lagrangian relaxation and the repeated cheapest path heuristic.
If the routes of the vehicles are not known, then we also need to create routes for the vehicles. The problem of routing vehicles and scheduling containers can be modelled as a multi-commodity network design problem on a time-space graph. Variable reductions, cutting planes and other additional constraints are looked into to make the problem easier to solve. Additions to the model are researched that can make the model more suitable for use in practice. Additionally, ILP based solution methods are developed. Finally, some of these
reductions, extensions and solution methods are implemented and reviewed.

With cockpit crew costs being the second largest costs of an airline, making optimal use of the available crew is very important. The productivity of the crew is limited by the labor agreement and law regulations, which prevent the crew members from working irregularly or excessively. In this thesis we present several methods to solve the crew scheduling problem as to calculate the crew productivity based on the labor agreements and law regulations.
The crew scheduling problem is decomposed into the crew pairing problem and the crew rostering problem. A set covering approach is used to solve the traditional crew pairing problem and a matching algorithm is used to solve the crew pairing problem that arises when we allow flights being retimed. The crew rostering problem is tackled by a minimum cost flow network method and a column generation approach. All the methods are tested on a variety of flight schedules deviating in the number of night flights included.

The cap set problem consists of finding the maximum size cap sets, i.e. sets without a 3-term arithmetic progression in F₃. In this thesis several known results on the behavior of this number as n → ∞ are presented. In particular we discuss a reformulation by Terence Tao and Will Sawin of a proof found by Dion Gijswijt and Jordan Ellenberg. It uses the slice rank, a rank that is defined for elements of tensor products, to give upper bounds on the size of the cap sets. In this report we will explain the slice rank and how it is related to the size of cap sets. We will also explore whether the slice rank might be used for bounding the size of arithmetic progression-free sets in F_q for q ≠ 3. We show that we can not use the slice rank to give a non-trivial upper bound on the size of n-term progression-free sets for n ≥ 7. This was already known for n ≥ 8.