Theory Seminar

Part 1: We formalize fairness for the \(k\)-server problem via \((\alpha,\beta)\)-fairness: each server’s cost is at most an \(\alpha/k\) fraction of the total plus \(\beta\). We show fairness can be achieved without losing competitiveness. Offline, we transform any optimal solution into a fair one with \(\alpha=1+\epsilon\) and \(\beta=O(diam \cdot \log k/\epsilon)\) while incurring only an additive \(O(diam \cdot k\log k/\epsilon)\) cost. Online, we convert any competitive algorithm into a randomized algorithm that is fair with high probability against an oblivious adversary, with only a small competitiveness loss. We also analyze classics: DCA is fair on lines and on trees for \(k=2\) but fails on general trees; on paging, FIFO is fair and marking algorithms (including LRU) satisfy a weaker fairness notion.

Part 2: We study the secretary problem with value predictions in both the standard random-order model (ROSP) and a learning-augmented model where the decision-maker can choose the arrival order based on predictions (COSP). We design a randomized algorithm that trusts predictions unless a large deviation is detected, then switches to a threshold rule. If \(\epsilon\in[0,1]\) bounds the multiplicative prediction error, we obtain competitive ratio \(\max\{0.221,\frac{1-\epsilon}{1+\epsilon}\}\) for ROSP (improving [Fujii Yoshida ‘23]) and \(\max\{0.262,\frac{1-\epsilon}{1+\epsilon}\}\) for COSP, demonstrating the benefit of combining predictions with arrival-order control.

In 1929, Gödel proved his celebrated completeness theorem, showing that in first-order logic a statement is true if and only if it has a finite proof. Exactly fifty years later, Cook and Reckhow asked whether a stronger phenomenon might hold in propositional logic: is there a fixed proof system—such as the sequent calculus or ZFC—in which every tautology admits a short proof? Equivalently, does NP = coNP? This question lies at the heart of propositional proof complexity, whose central goal is to show that for every proof system there exist tautologies that require exponentially long proofs.

In this talk, we survey a recent and successful line of work in proof complexity that connects the strength of proof systems to the complexity of combinatorial search problems. We will see how short proofs correspond to efficient algorithms (and conversely), and how this connection has been used to obtain new lower bounds in both proof complexity and circuit complexity. This talk is based on joint work with Noah Fleming, Toniann Pitassi, and Robert Robere.

Stefan is a fifth year PhD student at McGill University, advised by Robert Robere. His research is in computational complexity, with a focus on proof complexity and circuit lower bounds.

Previously, Stefan received his bachelor’s in computer science from UMass Amherst, and his Masters in mathematics from McGill.

While classical MWU and EXP3 algorithms for online learning and adversarial bandits achieve sqrt{T} poly(n) regret, they require O(n log(T)) space to implement, which is inefficient for modern large-scale applications. Recent work by Srinivas et al. [STOC’22]; Peng and Zhang [SODA’23]; Peng and Rubinstein [FOCS’23] has established polylogarithmic memory algorithms for the full-feedback setting (q=n, where q is the number of experts/bandits we can query at each step), but the limited feedback case (\(q < n\)) remains open.

In this talk, we present the first algorithms to achieve \(o(T)\) regret with \(o(n)\) memory for \(q < n\). In fact, all of our algorithms only require \(polylog(nT)\) memory. Our results include: (i) a \(T^{2/3}\) regret bound for the \(q=1\) bandit case, and the bound can be improved to the optimal \(\sqrt{nT}\) under random-order losses; (ii) a near-optimal \(\sqrt{nT}\) regret bound for \(q=2\); and (iii) generalizations to interval regret and sliding-window models. Our main techniques include using the estimated losses of the bandits for pool management and the separation of exploration and exploitation to remove dependency for boosting. These techniques might be of independent interest for the broader theory community.

Based on a joint work with Vladimir Braverman, Sumegha Garg, David P. Woodruff, and Samson Zhou (SODA 2026).

TBD

TBD

TBD

Edge crossings are the dominant source of visual clutter in graph drawings and are known to significantly hinder readability. A core goal in graph visualization is therefore to reduce the impact of crossings on the drawing. This is one of the fundamental problems in Computer Science, which, unfortunately, does not have a good solution for dense graphs, where many crossings are unavoidable. Beyond-planar graph theory attempts to classify graphs that do admit drawings in which crossings are limited in some way. In this talk, we focus on two prominent such families: k-planar graphs, that have drawings in which each edge is crossed at most k times (a purely combinatorial constraint), and right-angle crossing (RAC) graphs, that have drawings in which all crossings occur at a right angle (a geometric constraint that helps distinguish crossings easier). Although these classes are defined by very different principles, we will present a surprising relationship between them.

Myroslav Kryven is an Assistant Professor of Computer Science at Amherst College. His research lies at the intersection of theoretical and applied computer science, with interests in network visualization, parameterized algorithms, computational geometry, and pursuit–evasion games.

Previously, Myroslav was a postdoctoral researcher at the GADA Lab in the Department of Computer Science at the University of Manitoba, working with Stephane Durocher. Before that, he held postdoctoral positions at the University of Arizona with Stephen Kobourov and at the University of Würzburg with Alexander Wolff.

He earned his PhD in Network Visualization from the University of Würzburg (2016–2020), supervised by Alexander Wolff.

TBD

TBD

TBD

TBD

TBD

TBD

TBD

TBD

TBD

TBD

TBD

TBD

TBD

TBD