Prof. Roei Tell | Time vs Space vs Alternations: General Plasticity for Algorithms from Hardness ...

Prof. Roei Tell | Time vs Space vs Alternations: General Plasticity for Algorithms from Hardness ...

by Roei Tell · View the channel on PSI

Formal & Physical Sciences Computing & Cybersecurity UYComputer scienceUYAMathematical theory of computation
🎙 Roei Tell 👥 8K 📅 September 10, 2026 ⏱ 61 min 👁 4 📄 original study 🧭 2026-09-10
Available in: English (current) Français

Keywords

time-space trade-offrange avoidance problemalgorithmic rigiditylow-space complexityalternations

Summary

The seminar by Prof. Roei Tell (University of Toronto) addresses a recent surprising theorem by Ryan Williams showing that any algorithm running in time t on a multitape Turing machine can be simulated using O(sqrt(t)) space and 2^{O(sqrt(t))} time. This result challenges the traditional understanding of resource trade-offs in algorithms. Tell introduces the dichotomy between algorithmic rigidity (where resources cannot be compressed) and algorithmic plasticity (where resources can be traded). He presents new joint work with Jong Lee that provides evidence for plasticity under a hardness assumption related to the range avoidance problem. They show that under the assumed hardness of a new variant called ’low space avoid’, any algorithm running in time t can be simulated in space t^ε on average for arbitrary constant ε>0, and with sufficient alternations can be simulated in linear time. The talk extensively discusses the range avoidance problem, its known results, and the new hardness assumption, which is argued to be a natural and potentially minimal assumption. The results are conditional and highlight open questions about the limits of resource trade-offs in computation.

179 words

Critical Evaluation

Value of the Information & Strength of the Argument

The talk delivers high value by proposing a new hardness assumption (low space avoid) and deriving from it strong algorithmic plasticity results. The argumentation is systematic: it starts with a puzzling theorem, frames the logical extremes, and then builds a technical foundation. The speaker carefully dissects the assumption’s parameters, compares it with prior assumptions, and discusses its plausibility. The reasoning is clear and the presentation includes interactions with the audience clarifying technical points. The overall argument supports the thesis that algorithmic plasticity is a general phenomenon, albeit conditionally on an unproven hardness assumption. The talk is more than a results announcement; it offers a conceptual framework for understanding resource trade-offs.

Scientific Rigor, Source Quality, Title Accuracy

The talk is scientifically rigorous: it appropriately cites prior work (Ryan Williams, range avoidance literature, etc.) and explicitly acknowledges the conditional nature of the results. The sources are not listed in the description beyond the institute links, but the speaker references well-known results and authors in the field. The title closely matches the content, covering time, space, and alternations. No significant discrepancies are noted. The lack of full source list in the video description is a minor limitation, but the talk itself provides sufficient context.

210 words

Title / Content Match

The title accurately reflects the content: it focuses on the trade-off between time, space, and alternations in algorithms, and the concept of general plasticity derived from hardness of range avoidance.

Quality & Reliability

8/10

The talk is a research seminar at the Isaac Newton Institute, delivered by a professor at the University of Toronto. The content is technical and presents new results conditional on unproven assumptions. The presentation is rigorous and the speaker discusses prior work thoroughly.

Key Moments

Markers derived by PSI from the transcript: the creator did not define chapters.

Cited Sources

Contribution & Novelties

The talk introduces a new hardness assumption (low space avoid) that is argued to be weaker and more natural than existing assumptions. Under this assumption, it demonstrates that any algorithm can be simulated in sublinear space on average, and with enough alternations, in linear time. This substantially strengthens the case for algorithmic plasticity. The contribution is original and pushes the understanding of resource trade-offs, though it remains conditional.

Pour aller plus loin :

109 words

Radar Profile

The profile shows high technical level and strong information quality, with moderate quantity and reliability scores reflecting the conditional nature of the results. The speaker demonstrates deep expertise, but the novel findings depend on an unproven assumption, slightly lowering the reliability score.

Reliability 8/10