Results 1341 - 1350 of 23833

Many structured linear systems arise from problems in polynomial algebra. When this is the case, algorithms from computer algebra, such as the fast Fourier transform, can be used to design faster linear system solvers. In this talk, I will describe some recent work and open problems on the complexity of such structured linear systems.

Border rank is a measure of complexity of a tensor. A fundamental problem in theoretical computer science is to lower bound the border rank of explicit tensors. However, there is a barrier that limits the range of applicability of classical techniques. In the talk I will discuss a recent technique that is not subject to these barriers.

I will talk briefly about three topics I've worked on that fit the theme of this workshop, and what I'd like to work on next. First, I'll talk about the application of tensor rank to classic algorithmic problems such as set cover. Then I'll talk about the group--theoretic approach to prove that \omega = 2 and my attempts to show that it can't succeed. Finally, I'll talk about high-dimensional expanders and their application to proof complexity.

In this talk I will highlight three tightly linked fronts in algebraic complexity—Polynomial Identity Testing (PIT), polynomial factoring, and debordering—and how they bear on the algebraic  P vs  NP question (VP vs VNP). At their core lie linear-algebraic structures that power algorithms and explain barriers. I will very briefly discuss these connections and recent advances in structured settings.

In this talk we will briefly discuss online makespan minimization on unrelated machines. We will describe how one can obtain a 2+eps competitive solution with only an average of logarithmically many re-assignments per job, almost matching the best known offline approximation algorithm for this problem.

Parallel algorithms are crucial for processing large-scale datasets and solving complex problems efficiently.
As multi-core processors have become the norm, parallelism offers the potential to significantly accelerate computations in areas such as data science, social network analysis, and computational biology. However, achieving high performance and scalability in parallel computing remains a challenging task, especially when dealing with graphs of diverse structures. The inherent complexity of parallel graph algorithms demands innovative approaches to harness the full potential of modern hardware.

This thesis argues that shared-memory parallel algorithms and techniques can solve a wide array of fundamental graph problems and applications with proven efficiency and strong scalability to larger data sizes and increased parallel resources. We observe that many existing parallel graph solutions can even perform worse than optimal sequential algorithms on readily available parallel hardware and frequently encounter out-of-memory issues when processing large graphs due to excessive memory overhead.

To address these limitations, we identify and prioritize three critical properties for designing scalable and efficient parallel algorithms: synchronization-efficiency, space-efficiency, and work-efficiency. Our research philosophy, algorithm-system co-design, guides the development of solutions that achieve these goals. The thesis investigates various problems, including fundamental graph algorithms and data science applications. Most of our proposed algorithms are implemented and rigorously evaluated on real-world, large-scale datasets, some with billions of edges. Our experimental results consistently demonstrate superior practical performance and robust scalability with an increasing number of processor cores.