Show Notes
In this episode, Professor Pål Grønås Drange from the University of Bergen, introduces the field of Parameterized Complexity - a powerful framework for tackling hard computational problems by focusing on specific structural aspects of the input. This framework allows researchers to solve NP-complete problems more efficiently when certain parameters, like the structure of the graph, are "well-behaved". At the center of the discussion is the network diversion problem, where the goal isn't to block all routes between two points in a network, but to force flow - such as traffic, electricity, or data - through a specific path. While this problem appears deceptively similar to the classic "Min.Cut/Max.Flow" algorithm, it turns out to be much harder and, in general, its complexity is still unknown. Parameterized complexity plays a key role here by offering ways to make the problem tractable under constraints like low treewidth or planarity, which often exist in real-world networks like road systems or utility grids. Listeners will learn how vulnerability measures help identify weak points in networks, such as geopolitical infrastructure (e.g., gas pipelines like Nord Stream). Follow out guest: Pål Grønås Drange
More from Data Skeptic
The next evolution of wearable technology may not require new screens or controllers, but new ways to interact with the devices we already wear. Shimon explores how gesture-sensing earbuds could transform virtual reality and wearable computing through intuitive, user-centered interactions that make technology more accessible and adaptable.
How do we design robots and autonomous vehicles that understand the unwritten rules of human behavior? Kyle speaks with Cornell Tech professor Wendy Ju about implicit interaction, "Wizard of Oz" prototyping, and what studying pedestrians, self-driving cars, and even robotic furniture can teach us about designing technology that behaves the way people expect.
The data we collect about ourselves can tell us a lot—but only if the technology collecting it actually fits into our lives. Daniel Epstein explores personal informatics, from fitness trackers and food journals to baby tracking and AI, and explains why abandoning a tracking tool doesn't necessarily mean it failed.
In the final episode of our Recommender Systems season, we explore the growing questions of trust, manipulation, privacy, fairness, sustainability, and user control. From fake reviews and shilling attacks to explainable recommendations and user-selected algorithms, we look at what happens when recommender systems must answer not only for what they recommend, but for the consequences of those choices.
In part two of the Data Skeptic Recommender Systems season finale, Kyle asks a deceptively difficult question: what should recommender systems actually optimize for? Drawing on conversations from across the season, the episode explores engagement, filter bubbles, popularity bias, fairness, human curation, embeddings, and the growing role—and risks—of large language models in shaping what gets recommended to us.