DIMACS | Center for Discrete Mathematics and Theoretical Computer Science
Even after half a century of intensive research the computational complexity of many fundamental graph problems remains unsettled One of the main reasons is that our current frameworks for proving hardness i e conditional lower bounds do not yet work on these core problems This workshop aims to bring researchers
Evaluating the similarity or dissimilarity between strings stands as a prevalent theme within the computational aspects of string processing This theme finds practical implications across various domains including computational biology signal processing text retrieval image compression data mining and pattern recognition The Hamming Distance a natural metric for measuring similarity
Fine grained complexity theory aims to prove that for many different computational problems the current best algorithms cannot be substantially improved For many of the problems of interest including those at the core of the hardness assumptions used throughout the theory the best known algorithm is algebraic in nature using
Fair division of indivisible items is a central problem in algorithmic game theory, with many natural applications in resource allocation. Unlike divisible resources, indivisible items cannot always be allocated in
Quantum circuits inherently perform linear algebra operations on quantum states, suggesting the potential for executing numerical linear algebra computations on quantum computers. However, existing quantum algorithms often rely on specific
Historical development of major ideas of quantum physics - the so-called two quantum revolutions (1924-28) - will be outlined from a modern mathematical perspective. Connection of old quantum mechanics by
We study the problem of estimating the size of the maximum matching in the sublinear-time setting. This problem has been extensively studied, with several known upper and lower bounds. A
In this seminar, we will provide a brief introduction to the early history of series with sums of 1/π and 1/π2, we meet Ramanujan, and discuss the role played by
We introduce the problem of learning conditional averages in the PAC framework. The learner receives a sample labeled by an unknown target concept from a known concept class, as in
I will quickly review discrete Fourier analysis and use it to prove an analogue of Roth's theorem on sets not containing 3-term arithmetic progressions in the finite field vector space
