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.

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

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

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

Anselm Blumer

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

Michael Joseph

Arsalan Motamedi

Christopher Ratigan

Mingqian Chen

Dale Jacobs

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

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

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

Physics & Computation Reading Group

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.

- Algorithms
- Advanced Algorithms
- Computation Theory
- Computational Geometry
- Advanced Computational Geometry
- Seminar in Quantum Information Science
- Quantum Computer Science
- Quantum Complexity Theory
- Theoretical Computer Science Toolkit
- Anonymous Communications Theory
- Graph Theory
- Convex Optimization