Events

Name: Brandon Dos Remedios

Date: Jul 23, 2025

Time: 10:00 AM

Location: 202

Supervisor: Chen Greif

Thesis Title: Precision-cascading in Restarted GMRES

Abstract: Iterative linear solvers are a key paradigm, developed within numerical linear algebra, for solving linear systems within a multitude of applications. Alongside this, mixed-precision is a growing novel field of methodology which utilizes non-standard precision configurations to modify algorithms and tune their characteristics. In this thesis, we propose a simple inter-iteration approach to applying mixed-precision concepts towards general iterative linear solvers, called precision-cascading. This approach involves executing an algorithm in a sequence of increasingly accurate hardware-supported precision formats, tightening precision based on tracked solver runtime metrics, to iteratively build towards an accurate calculated solution while extracting cost improvements from early low-accuracy high-speed precision formats. We contribute a formal articulation of this idea and a large robust GPU-accelerated code base to facilitate its experimental study. Using the code base, 36,480 linear solve experiments are executed and analyzed to understand the approach's comparative effectiveness, relative to a fixed-precision double control solver, within its application to the GMRES(m) algorithm. Experimentation supports the hypothesis that the precision-cascading approach can match solution accuracy and can improve computational cost relative to the performance of the control fixed-precision double approach. This specifically consists of high fractions of precision-cascading experiments complying with a strict fractional error threshold to solution accuracy from the corresponding control solver, and within such compliant experiments, precision-cascading experiments achieving up to 22% median computational cost improvements. Additional key insights into the convergence behaviour effects of ILU-preconditioning, differing phase sequences, and differing phase transition logic approaches, are also explored through the thesis experimentation.

Name: Seyed Ali Tabatabaee

Date: Tuesday, 22 July 2025

Time: 11:00 am to 2:00 pm

Location: ICCS 202

Zoom Link: https://ubc.zoom.us/j/66090771145?pwd=Sl7SFFGVZXdzJKIGBTaYoJSBt05i44.1

Thesis Title: Optimization with Explorable Uncertainty

Abstract:

Many real-world problems involve elements (e.g., clients, jobs, etc.) with uncertain properties. Acquiring more accurate properties of these elements is often costly but sometimes necessary for high-quality solutions. The goal is to find such solutions through cost-effective strategies for obtaining more accurate information. The described model is often referred to as explorable uncertainty. This thesis studies optimization problems from the domains of facility location and job scheduling in the explorable uncertainty model. First, we study center problems with moving entities of bounded speed in Euclidean space, where the movement of the entities is unpredictable and processing must be done in real-time. Center problems involve determining the location of a facility to serve a set of entities while optimizing a specified objective function. In particular, we investigate computing the 1-center, centroid, center of mass, and 1-median for a set of moving entities. Next, motivated by the connections observed between these problems and perpetual scheduling problems, we shift our focus to study the latter in more depth. Perpetual scheduling problems involve jobs that require recurring processing. The goal is to process these jobs while optimizing a specified objective function. More specifically, we investigate two prominent examples of perpetual scheduling problems, namely the bamboo trimming problem and the windows scheduling problem, in settings that have not been considered before. Finally, we study these two scheduling problems in the model of explorable uncertainty, where jobs’ processing requirements can be reduced by taking some actions. We provide novel algorithms for the problems considered throughout this thesis. Our results contribute to a better understanding of the various forms of explorable uncertainty and the additional intricacy introduced to optimization problems when considered in this model.

Name: Tony Mason

Date: July 21, 2025

Time: 13:00-16:00

Location: ICCS 246

Supervisor: Margo Seltzer

Title: Indaleko: The Unified Personal Index

Abstract:
Digital data overload—1.7MB generated per second, 361 billion emails daily in 2024—forces users to waste up to 25% of their time searching for or recreating files. Scattered across devices, cloud services, and inconsistent interfaces, data is nearly impossible to find, like a six-month-old document with no recalled name or location. To address this, I propose the Unified Personal Index (UPI), a system that unifies storage metadata, semantic metadata from file content, and human activity context from user interactions. Unlike siloed cloud searches, the UPI creates a single, human-centric index that transcends storage boundaries, aligning retrieval with how we remember.

Implemented via the Indaleko prototype, the UPI uses natural language processing and activity tracking to collect and query metadata across platforms, enabling intuitive searches like “find files edited on my phone while traveling.” Ongoing evaluations are validating superior retrieval effectiveness, leveraging activity context to match experiential cues. By mirroring human memory processes, the UPI simplifies finding and lays the foundation for advanced tools capable of leveraging its abilities to enable finding. The UPI redefines digital retrieval, transforming searching into finding as naturally as we recall a moment.

Name: Abner Turkieltaub

Date: Monday, July 21

Time: 9 am

Location: ICCS 146

Zoom: https://ubc.zoom.us/j/69647724028?pwd=0EvAbvIf3M5Jh2b6MbhvOmYCGTYZ8L.1

Meeting ID: 696 4772 4028 Passcode: 857844)

Supervisor: Bruce Shepherd

Title: Hiring Under Uncertainty and Competition

Abstract:

In this dissertation, we study different online hiring problems related to the Secretary Problem. In the Secretary Problem, an employer sees a sequence of candidates. Each time a new candidate arrives, the employer makes an irrevocable choice on whether to hire based only on the relative ranking of the candidates seen so far. The employer tries to maximize the probability of hiring the best. It is known that the optimal strategy hires the best with probability 1/e . We study several extensions. For many of them, we work on an infinite arrival regime. This allows us to apply a lemma we prove characterizing the number of “promising candidates” in any given time interval.

For a single employer trying to hire k candidates, we produce a tight analysis of some simple strategies. We also study in detail the case k = 2. We derive an optimal algorithm under the objective known as “probability-competitiveness”. We also study the case in which the two selected candidates must be independent in a given matroid.

For multiple employers we consider three models. First, for employers seeing the same sequence of candidates, we compute Nash Equilibria for two and three employers. We also derive general properties of the Nash Equilibria for any number of employers. For employers seeing the same set of candidates, but in different order, we compute a Nash Equilibria for two employers.

Finally, we consider employers

with different sets of candidates, competing for whom hires first while trying to get their best candidate.

As motivation, imagine different research groups within the same department trying to hire someone in their area. We show that without any regulation, competition pushes employers to hire too early, making extremely unlikely the hiring of a top candidate. We also compute the social optimum and propose different regulations that incentivize employers to align with the social optimum.

Finally, we study oblivious Online Contention Resolution Schemes (OCRSs) for matroids. This problem has an interesting link to the Matroid Secretary Conjecture. We provide an optimal 1/e-selectable oblivious OCRS for selecting a single item. We also prove non-existence of constant-selectable oblivious OCRSs for general matroids.