Computer Science seminars

Katarzyna Swirydowicz uses an asynchronous solver on an AMD system to examine the practical implementation of computational linear algebra across CPUs and GPUs. The talk introduces the relevant computational ideas, programming models, and software tools, then considers how algorithmic structure interacts with hardware capabilities. This case study illustrates both the opportunities and implementation challenges of asynchronous methods for large-scale scientific computing on GPU-accelerated systems.

Zander Kelley presents joint work with Xin Lyu separating randomized and deterministic three-player communication in the number-on-forehead model. Earlier work by Kelley, Lovett and Meka gave an explicit function with an efficient randomized protocol but a deterministic lower bound of Ω(n^(1/3)). The argument studies whether its yes-instances can be covered efficiently by small cylinder intersections. A sifting lemma finds a denser induced subgraph inside a bipartite graph with large grid norm. An improved version raises the communication lower bound to Ω(n^(1/2)). The key structural result covers small cylinder intersections by a few reasonably small slice functions; the talk compares this simplification with Szemerédi’s triangle removal lemma.

Matrix multiplication underpins scientific computing and artificial intelligence, yet practical numerical libraries and hardware accelerators commonly retain the classical cubic-time algorithm despite decades of subcubic theoretical advances. This talk reviews the effort to make faster multiplication algorithms useful in practice. It examines why arithmetic complexity alone does not determine performance: some algorithms require enormous matrices or incur large hidden constants, while communication costs, numerical stability and the match between software and hardware create additional obstacles. The historical perspective connects asymptotic algorithm design to actual performance and power consumption.

Brain Emulation Challenge workshop will tackle cutting-edge topics such as ground-truthing for validation, leveraging artificial datasets generated from virtual brain tissue, and the transformative potential of virtual brain platforms, such as applied to the forthcoming Brain Emulation Challenge.

Brain Emulation Challenge workshop will tackle cutting-edge topics such as ground-truthing for validation, leveraging artificial datasets generated from virtual brain tissue, and the transformative potential of virtual brain platforms, such as applied to the forthcoming Brain Emulation Challenge.

Nearest-neighbor indexes usually rely on a single distance function, but accurate comparisons can be expensive. This talk proposes a bi-metric framework: a cheap proxy metric builds the index, while the query procedure uses a limited number of evaluations of both the proxy and an expensive ground-truth metric. The theory applies to DiskANN and Cover Tree. When the proxy approximates the ground-truth metric within a bounded factor, the resulting structure can achieve arbitrarily good approximation guarantees under the accurate metric. Experiments on text retrieval using models with very different computational costs show improved accuracy-efficiency tradeoffs on almost all MTEB datasets compared with alternatives such as reranking. Joint work with Haike Xu and Sandeep Silwal.

Biologically plausible spiking neural networks (SNNs) are an emerging architecture for deep learning tasks due to their energy efficiency when implemented on neuromorphic hardware. However, many of the biological features are at best irrelevant and at worst counterproductive when evaluated in the context of task performance and suitability for neuromorphic hardware. In this talk, I will present an alternative paradigm to design deep learning architectures with good task performance in real-world benchmarks while maintaining all the advantages of SNNs. We do this by focusing on two main features – event-based computation and activity sparsity. Starting from the performant gated recurrent unit (GRU) deep learning architecture, we modify it to make it event-based and activity-sparse. The resulting event-based GRU (EGRU) is extremely efficient for both training and inference. At the same time, it achieves performance close to conventional deep learning architectures in challenging tasks such as language modelling, gesture recognition and sequential MNIST.

How could machines learn as efficiently as humans and animals? How could machines learn to reason and plan? How could machines learn representations of percepts and action plans at multiple levels of abstraction, enabling them to reason, predict, and plan at multiple time horizons? I will propose a possible path towards autonomous intelligent agents, based on a new modular cognitive architecture and a somewhat new self supervised training paradigm. The centerpiece of the proposed architecture is a configurable predictive world model that allows the agent to plan. Behavior and learning are driven by a set of differentiable intrinsic cost functions. The world model uses a new type of energy-based model architecture called H-JEPA (Hierarchical Joint Embedding Predictive Architecture). H-JEPA learns hierarchical abstract representations of the world that are simultaneously maximally informative and maximally predictable.

We examine consciousness from the perspective of theoretical computer science (TCS), a branch of mathematics concerned with understanding the underlying principles of computation and complexity, including the implications and surprising consequences of resource limitations. We propose a formal TCS model, the Conscious Turing Machine (CTM). The CTM is influenced by Alan Turing's simple yet powerful model of computation, the Turing machine (TM), and by the global workspace theory (GWT) of consciousness originated by cognitive neuroscientist Bernard Baars and further developed by him, Stanislas Dehaene, Jean-Pierre Changeux, George Mashour, and others. However, the CTM is not a standard Turing Machine. It’s not the input-output map that gives the CTM its feeling of consciousness, but what’s under the hood. Nor is the CTM a standard GW model. In addition to its architecture, what gives the CTM its feeling of consciousness is its predictive dynamics (cycles of prediction, feedback and learning), its internal multi-modal language Brainish, and certain special Long Term Memory (LTM) processors, including its Inner Speech and Model of the World processors. Phenomena generally associated with consciousness, such as blindsight, inattentional blindness, change blindness, dream creation, and free will, are considered. Explanations derived from the model draw confirmation from consistencies at a high level, well above the level of neurons, with the cognitive neuroscience literature. Reference. L. Blum and M. Blum, "A theory of consciousness from a theoretical computer science perspective: Insights from the Conscious Turing Machine," PNAS, vol. 119, no. 21, 24 May 2022. https://www.pnas.org/doi/epdf/10.1073/pnas.2115934119

Engineering designers practice design-by-analogy (DbA) during concept generation to retrieve knowledge from external sources or memory as inspiration to solve design problems. DbA is a tool for innovation that involves retrieving analogies from a source domain and transferring the knowledge to a target domain. While DbA produces innovative results, designers often come up with analogies by themselves or through serendipitous, random encounters. Computational support systems for searching analogies have been developed to facilitate DbA in systematic design practice. However, many systems have focused on a query-based approach, in which a designer inputs a keyword or a query function and is returned a set of algorithmically determined stimuli. In this presentation, a new analogical retrieval process that leverages a visual interaction technique is introduced. It enables designers to explore a space of analogies, rather than be constrained by what’s retrieved by a query-based algorithm. With an exploration-based DbA tool, designers have the potential to uncover more useful and unexpected inspiration for innovative design solutions.

In the Learning Salon, we will discuss the similarities and differences between biological and machine learning, including individuals with diverse perspectives and backgrounds, so we can all learn from one another.

In the Learning Salon, we will discuss the similarities and differences between biological and machine learning, including individuals with diverse perspectives and backgrounds, so we can all learn from one another.

In the Learning Salon, we will discuss the similarities and differences between biological and machine learning, including individuals with diverse perspectives and backgrounds, so we can all learn from one another.

A rich data representation that finds wide application in industry and research is the so-called knowledge graph - a graph-based structure where entities are depicted as nodes and relations between them as edges. Complex systems like molecules, social networks and industrial factory systems can be described using the common language of knowledge graphs, allowing the usage of graph embedding algorithms to make context-aware predictions in these information-packed environments.

Neuroscience is witnessing extraordinary progress in experimental techniques, especially at the neural circuit level. These advances are largely aimed at enabling us to understand precisely how neural circuit computations mechanistically cause behavior. Establishing this type of causal understanding will require multiple perturbational (e.g optogenetic) experiments. It has been unclear exactly how many such experiments are needed and how this number scales with the size of the nervous system in question. Here, using techniques from Theoretical Computer Science, we prove that establishing the most extensive notions of understanding need exponentially-many experiments in the number of neurons, in many cases, unless a widely-posited hypothesis about computation is false (i.e. unless P = NP). Furthermore, using data and estimates, we demonstrate that the feasible experimental regime is typically one where the number of experiments performable scales sub-linearly in the number of neurons in the nervous system. This remarkable gulf between the worst-case and the feasible suggests an algorithmic barrier to such an understanding. Determining which notions of understanding are algorithmically tractable to establish in what contexts, thus, becomes an important new direction for investigation. TL; DR: Non-existence of tractable algorithms for neural circuit interrogation could pose a barrier to comprehensively understanding how neural circuits cause behavior. Preprint: https://biorxiv.org/content/10.1101/639724v1/…

Finding similar item pairs is a core task in recommendation systems. It can be expressed as finding large inner products in a collection of vectors, or large entries in a matrix product. This talk describes how randomized sampling ideas became a distributed algorithm used in Twitter’s production recommendation system. Existing approaches struggled with industrial-scale inputs containing hundreds of billions of nonzero entries. The algorithm combines low-dimensional projections, called hashes, with path-sampling techniques, called wedges. The presentation explains the mathematical ideas behind this combination and its application at production scale. Joint work with Aneesh Sharma of Twitter and Ashish Goel of Stanford.

Theory for high-dimensional nearest-neighbor search often assumes a known search radius, a specified approximation ratio, and a request for one nearby point. Practical applications instead ask for the exact k nearest points without knowing the relevant radius; an appropriate approximation parameter also depends on the data distribution. Existing reductions between these formulations introduce polylogarithmic time or space overhead that can make them unattractive in practice. This talk presents simple, more efficient reductions that solve k-nearest-neighbor search using locality-sensitive hashing and address this gap between theoretical guarantees and practical queries. Joint work with Tobias Christiani and Mikkel Thorup.

This talk establishes a general reduction from nonlinear spectral gaps of metric spaces to data-dependent space partitions in the form of locality-sensitive hashing. The reduction yields an approach to high-dimensional approximate near-neighbor search and a data structure for any d-dimensional norm whose query algorithm makes a sublinear number of probes. Its approximation factor is O(log d), improving on the square-root-of-d factor available from the generic approach based on John’s ellipsoid. The presentation connects spectral properties, geometric partitions, and efficient approximate search. Joint work with Assaf Naor, Aleksandar Nikolov, Ilya Razenshteyn, and Erik Waingarten.