Tufts CS Theory Group

    Logo

This is the website of the CS Theory group at Tufts University. Our research area covers various topics in theoretical computer science, including algorithms, computational complexity, cryptography, quantum computations, computational geometry.

Positions

We are currently recruiting PhD students to start in September 2024 (application deadline is December 15). Further information can be found here.

Faculty

Megumi Ando
Theoretical foundations of anonymous communications

Lenore Cowen
Data science, graph algorithms, approximate routing, classification and clustering for high-dimensional data, coloring and its generalizations, computational molecular biology

Saeed Mehraban
Quantum information and computation, quantum complexity theory, quantum pseudo-randomness

Vladimir Podolskii
Computational complexity, ontology-mediated queries, min-plus geometry

Diane Souvaine
Computational geometry, design and analysis of algorithms, computational complexity

Theory-Associated Faculty

Prosenjit Bose
Вiscrete and computational geometry, algorithms, data structures, graph theory

Peter Love
Quantum algorithms, quantum simulation

Kasso Okoudjou
Applied and computational harmonic analysis, cpectral analysis of Laplacian-based operators on graphs and fractals, quantum walks on graphs and fractals

Samantha Petti
Computational biology, probability and statistical inference, design and analysis of algorithms

Csaba D. Tóth
Discrete and computational geometry, combinatorial algorithms

Faculty Emeriti

Anselm Blumer
Machine learning, information theory, data compression, string algorithms, computational biology

PhD Students

Andrei (Andrew) Gonczi

Michael Joseph

Arsalan Motamedi

Christopher Ratigan

Master's Students

Mingqian Chen

Dale Jacobs

Theory Seminar

In Spring 2024 Theory Meetings are on Thursdays at 1:30-2:30PM. Please contact Vladimir Podolskii to join mailing list.

Quantum Information Seminar

Spring 2024 time: TBA. Please contact Saeed Mehraban to join mailing list.

Computational Geometry Meetings

Spring 2024 time: TBA. Please contact Diane Souvaine to join mailing list.

Past Reading Groups

Physics & Computation Reading Group

Past talks

December 7 2023, 9:30-10:30AM

Daniel Mitropolsky (Columbia), The Simplest Neural Models, and a Hypothesis for Language in the Brain

Location: JCC 170

Abstract. How do neurons, in their collective action, beget cognition, as well as intelligence and reasoning? As Richard Axel recently put it, we do not have a logic for the transformation of neural activity into thought and action; discerning this logic as the most important future direction of neuroscience. I will present a mathematical neural model of brain computation called NEMO, whose key ingredients are spiking neurons, random synapses and weights, local inhibition, and Hebbian plasticity (no backpropagation). Concepts are represented by interconnected co-firing assemblies of neurons that emerge organically from the dynamical system of its equations. We show that it is possible to carry out complex operations on these concept representations, such as copying, merging, completion from small subsets, and sequence memorization. I will present how to use NEMO to implement an efficient parser of a small but non-trivial subset of English (leading to a surprising new characterization of context-free languages), and a more recent model of the language organ in the baby brain that learns the meaning of words, and basic syntax, from whole sentences with grounded input. We will also touch on lower bounds in the model, and the idea of a fine-grained complexity theory of the brain.

List of theory-related courses at Tufts

Quantum Information Science Blog