Colloquia and Seminars

In the Degree Realization problem with respect to a family P of graphs the input is a non-increasing sequence d = (d1, . . . , dn) of positive integers, and the goal is to decide whether there exists a simple undirected graph G ∈ P, whose degrees correspond to d, i.e., such that deg(G) = d. In this paper we consider the version of Degree Realization in which the realization is required to be a forest (i.e., P is the family for forests). We consider optimized Degree Realization in which the goal is to obtain a realization that minimizes an objective function f. That is, the goal is to find a realization G that minimizes f(G) among the realizations of the given input sequence. More specifically, we focus on the following functions: the size of an optimal vertex cover and the size of an optimal dominating set. We also consider the total and paired versions of both Min Vertex Cover and Min Dominating Set. We provide characterizations and linear time realization algorithms for all the above-mentioned problems.

Existing tools for automatic detection of speculative leakage in commercial CPUs cannot be used for fuzzing indirect control flow instructions such as indirect branches, function calls, and returns. This is a fundamental limitation: fuzzers require exhaustive exploration of all possible control paths, potentially encountered during (mis)speculation. This becomes infeasible when any address can be a branch target.

We present Flowvizor, the first fuzzer that enables systematic investigation of Spectre-V2-type leakages in commercial CPUs. Our main insight is that the traditional black-box approach of existing tools can be augmented with the publicly available µarch knowledge of specific CPU components, such as branch predictors. By simulating these components when generating inputs to the fuzzer, Flowvizor achieves an exponential reduction of the fuzzing space down to hardware-reachable execution paths. Flowvizor's coverage improves with the accuracy of the µarch simulation and remains strictly larger than that of Revizor, the state-of-the-art black-box CPU fuzzer.

Flowvizor automatically unveils a new speculation trigger and a leak in Intel's CPU indirect branch predictor, it independently rediscovers several known leaks, offers new insights into the branch predictor μarch, and corroborates recently published reverse-engineered details about its internals. It opens new opportunities for systematic refinement of the reverse-engineered microarchitectural structures, providing code examples that cannot be explained by the public knowledge of CPU internals.

Deep Neural Networks remain highly susceptible to perturbation-based attacks, which seek small input modifications that induce model failure. These attacks manifest as either individual or universal adversarial perturbations (IAPs, UAPs), where the former are designed for specific inputs, whereas the latter are input-agnostic. While the simpler setting of IAPs has seen rapid methodological progress, UAP advancements remain comparatively limited, as adapting methods to the universal setting is often nontrivial. In this work, we propose Universal Perturbation Distillation (UPD), a domain-decoupled formulation for learning universal adversarial perturbations from off-the-shelf IAP methods. By treating individual adversarial examples as representation-level supervision, UPD leverages IAP techniques for the universal setting. We instantiate UPD on both large language model jailbreak as well as on image classification settings, achieving and often surpassing state-of-the-art performance, with substantial improvements on robust models.

Molecular dynamics simulations are computationally expensive, but optimizing them requires more than preserving exact program behavior. Many useful changes alter numerical trajectories while still preserving the physical properties that matter for a given simulation, such as energy stability, reversibility, or ensemble-level statistics.

We present a source-to-source optimization framework that searches for faster molecular dynamics implementations under physics-aware validation. The framework combines equivalence-preserving rewrites with stochastic program mutations that deliberately explore beyond ordinary semantic equivalence. For each candidate, a staged verifier checks both structural requirements and simulation-specific physical behavior, while a population-based search balances runtime, physical deviation, and program simplicity.

In this lecture, we study knapsack problems with departures under the online with a sample model. We begin with the fundamental special case of the Temp Secretary Problem with departures, where we obtain a constant competitive ratio of 1/8, providing the first performance guarantee for general instances of this problem.

We then extend our approach to the d-dimensional Online Vector Generalized Assignment Problem with Departures (VGAPWD), achieving a competitive ratio of 1/(16d) for d-dimensional resources. Lastly, we study the Multiple Knapsack Problem With Departures, which is a special case of VGAP.

For this special case, we present a more practical modification of our algorithm that achieves the same competitive ratio. Using extensive simulations on workloads derived from real cluster traces, we demonstrate that our algorithms consistently outperform state of the art algorithms and widely used heuristics, achieving typical improvements of 10–25% in total value compared to state of the art approaches.

These results demonstrate that the online with a sample paradigm successfully translates into algorithms that leverage historical data for improved empirical performance. This is aligned with the stronger theoretical guarantees we can prove within this framework.

Modern software engineering agents solve tasks by interleaving reasoning with API calls that observe and modify their environment. On long-horizon tasks this degrades performance: the context fills with API documentation, authentication flows, and parameter details, forcing the agent to interleave reasoning about the task with discovery of the interface used to solve it, a conflict that compounds into failure.

We introduce SCOPE, an approach that decouples task analysis from implementation by a method of API transpiling. A planner agent first reasons about the task in isolation, defines a focused set of environment interactions it requires, and transpiles the raw APIs into a compact, task-specific toolset, verifying each tool before handoff. A solver agent then operates over this narrowed
interface, free of extraneous API documentation and complicated workflows.

On the AppWorld Benchmark with Minimax-M2, SCOPE reaches 81% accuracy on test_normal, a 5-point gain over a vanilla ReAct baseline under identical conditions, and a 71% accuracy on test_challenge, a 6-point gain over the baseline, while shortening solver trajectories by 48% and collapsing the exposed API surface from 74 endpoints to 4 task-specific tools on average.