Results 1351 - 1360 of 23833

Oblivious Routing has a long history in both the theory and practice of networking. Meanwhile, Reconfigurable Networks are a new architecture that has recently come to the fore in data center networking due to their increased energy efficiency and scaling potential. In this talk, I will examine Oblivious Routing in the context of Reconfigurable Networks from a theoretical perspective, and briefly touch on some solved problems and open results.

A data structure is history independent if its internal representation reveals nothing about the history of operations beyond what can be determined from the current contents of the data structure. History independence has a rich history of study as a security guarantee, with the intent being to minimize risks incurred by a breach or audit. In recent work, history independence has also been used as an algorithmic tool, by hiding information from an oblivious adversary in order to produce faster data structures. In this talk, I will present examples of my work in both of these applications of history independence in data structures, followed by some questions of interest for future work.

I will give a brief overview of fine-grained complexity and algorithms, and mention some results related to graph theory, combinatorial optimization, and string pattern matching. These results often rely on algebraic algorithms such as Fast Fourier Transform and fast matrix multiplication.

My research focuses on building systems with strong theoretical foundations. I am engaged in the design, analysis, and implementation of algorithms and systems.

A major emphasis of my work is on processing-near-memory (PNM) architectures. PNM offers an alternative computing paradigm that reduces data movement by integrating lightweight compute units close to memory. To support large memory capacities, practical systems often incorporate multiple memory modules, resulting in a distributed architecture with a central processor and numerous memory-side cores. While extensive research exists on hardware implementations of PNM, few studies address these systems from a theoretical perspective. To bridge this gap, we propose a computational model for PNM systems and demonstrate that significant reductions in data movement can be achieved through careful data placement and task scheduling. We have designed several indexing algorithms tailored for PNM and implemented them on UPMEM’s commercial hardware. The results confirm that our approach effectively reduces data movement, both theoretically and empirically. I am also interested in applying PNM techniques to address memory-related challenges in other systems, as well as in deriving fundamental principles for the design of PNM algorithms.

Additionally, I work on learned indexes, an emerging research topic that uses instance-optimized models to represent datasets, thereby enabling efficient operations for data drawn from easy-to-learn distributions. My goal is to design learned indexes that are robust to skew, support incremental updates, and allow incremental modifications. As a first step, we have developed a new structure that greatly reduces model complexity on simple datasets by improving how noise is handled. I am open to collaborations on developing updatable learned index structures, as well as on exploring other forms of instance-optimized algorithms.

Multiprocessor computations are ubiquitous in today's world, forming the backbone of everything from resilient cloud systems and cryptocurrencies to efficient computation on personal computers and phones. However, despite its importance, there is a large gap between theory and practice in this field. In this talk I will briefly introduce the field of multiprocessor computing and discuss key challenges that theory in this field must overcome in order to better inform practice.

Suppose we have a structured, unknown matrix $A$ that we can only query with matrix-vector products $x \mapsto Ax$ and $y \mapsto A^\top y$. How can we recover $A$ using as few of these queries as possible? There is a wealth of work surrounding this question in numerical linear algebra, particularly for low-rank and sparse structures. However, a relatively new motivation stems from operator learning, where one wishes to learn unknown solution operators of PDEs from only operator-function products, i.e., data arising from simulations or experiments. In this setting, there is a vast theory-practice gap, and matrix recovery can help us derive provable guarantees for the infinite-dimensional analogue of this problem. In particular, we hope to understand whether operator learning techniques for scientific machine learning are computationally feasible or even advisable. I will discuss our recent work in this direction, as well as some open questions.

Over the past twenty years, randomized dimensionality reduction, frequently called sketching, has established itself as a fundamental tool in computational linear algebra. Yet basic questions in the mathematical theory of sketching still remain. This talk will survey the author's personal experience using and developing sketching algorithms. It will also discuss the gap between theory and practice in sketching and highlight open problems.

What is the optimal algorithm for computing the eigenvalues/eigenvectors of an arbitrary matrix? What about the singular value decomposition (SVD)? What does optimal even mean in this context?  I'll survey some recent efforts to answer these questions, from both a theoretical computer science and classical numerical analysis perspective. I'll also discuss related open research directions; despite the fact that the earliest eigenvalue algorithms date back nearly 200 years, there's still lots to be discovered here!

Data movement is often the dominant cost (in both time and energy) for tensor operations. A long line of work has gone into both reducing this cost and finding bounds on it, largely using geometric and graph-based methods. This talk describes a different approach to this problem using tools from information theory and database theory, and how these techniques can be applied to sparse linear algebra problems.