11
$\begingroup$

I am a graduate student in theoretical computer science, and in particular, approximation algorithms. I find now that I am more interested in pure math (I can say this because I seem to have enjoyed math courses more than the CS courses). I would like to ask if there are areas in theoretical computer science which are pretty much pure math (to be more precise, an area that is of interest in pure math on it's own without considering the applications to CS), or if I need to consider a major switch. I am already two and a half years into the program, so I am not sure if a switch would be a good idea at this point.

The only such thing I could find was graph minor theory, from browsing acceptance lists of top conferences. But that doesn't count as an 'area' for me that I can just focus on.

$\endgroup$
  • 3
    $\begingroup$ Any area of computer science involving pure math is likely to be motivated more by computer science than pure math. Consider Hamiltonian Cycles: what can be purer math than to care about cycles traversing an entire graph's vertices? If this has connections to logic, is this not still more excellent from a pure maths perspective? Yet how could you be more entrenched in CS than to contemplate HAMCYCLE? $\endgroup$ – Niel de Beaudrap May 2 '15 at 4:51
  • 5
    $\begingroup$ "I can say this because I seem to have enjoyed math courses more": I dont think this gives a good enough idea about what bothers you in TCS in order to answer your question. There are many many things that are of interest both to TCS and math communities, but the questions being asked are usually a little different. Also it's not clear to me why graph minor theory is not an area you can focus on? $\endgroup$ – Sasho Nikolov May 2 '15 at 5:35
  • 5
    $\begingroup$ In any case, some ideas: metric embeddings; Fourier analysis on finite abelian groups; Markov chains on a discrete/finite state space. $\endgroup$ – Sasho Nikolov May 2 '15 at 5:37
  • $\begingroup$ somewhat related Examples of “Unrelated” Mathematics Playing a Fundamental Role in TCS? $\endgroup$ – vzn May 5 '15 at 18:39
  • $\begingroup$ Regarding the risk of switching, maybe Academia stack Exchange would be more suitable? $\endgroup$ – Clément May 11 '15 at 7:34
12
$\begingroup$

Here are three more fields that fit your criteria.

  • Category theory. This is clearly interesting to most pure maths fields, but also has been very influential in the theory of (functional, sequential) programming languages.

  • Logic, particularly proof theory. The connections with computer science are too many to name, but logic is not only a rich field of pure mathematical, but the foundation of mathematics.

  • Number theory, the "queen of mathematics", which was deemed to be devoid of applications ... until cryptography came along.

$\endgroup$
  • $\begingroup$ note re logic see esp descriptive complexity theory (wikipedia) $\endgroup$ – vzn May 6 '15 at 3:32
  • $\begingroup$ I'm not sure that category theory (esp. as used in CS) is interesting to most math fields at the research level, even if it gets used as a basic language in several areas. For example, although category theory clearly shows up at the research level in (some) algebraic geometry and representation theory, that kind of category theory is very different than the kind used in computer science, as far as I can tell. $\endgroup$ – Joshua Grochow May 6 '15 at 15:47
  • 1
    $\begingroup$ @JoshuaGrochow That's partly true, but that's in parts because it's work in progress. There are tantalising hints that point towards deeper integration: (1) Voevodsky's univalent foundations try and unify the ideas of path in homotopy theory with proofs in logic; (2) the coalgebraic theories of real numbers by Pavlovic et al; (3) categorical foundations of quantum mechanics, see e.g. "Physics, Topology, Logic and Computation: A Rosetta Stone" by Baez and Stay. $\endgroup$ – Martin Berger May 6 '15 at 16:11
9
$\begingroup$

Yes: Graph theory, computational geometry, complexity theory, combinatorics are the things I research on in CS. Vector spaces and measure theory could be useful in theoretical machine learning too.

There is a lot more pure maths employed in theoretical CS, but they don't hit the news as often like AI and machine learning, which is why you don't hear about them much.

I personally switched over to CS from physics and pure math (yes, like abstract algebra kind of math), and never cease to find interesting problems.

$\endgroup$
  • 1
    $\begingroup$ And I would add Discrete Geometry to this list. $\endgroup$ – Sariel Har-Peled May 3 '15 at 22:27
7
$\begingroup$
$\endgroup$
  • 2
    $\begingroup$ Why the quotes around "mathematical"? $\endgroup$ – Joshua Grochow May 6 '15 at 15:41
  • $\begingroup$ in some areas it can be difficult to differentiate "(T)CS" content from "mathematical" as the question poses, the end of that sentence should be "leading investigators are [nearly] more mathematicians than computer scientists"; the two fields are slowly blending in many ways, this can be seen over the 20th century & it is continuing/ increasing in the 21st century. an ongoing fusion probably worthy of an entire book & some come close (eg Davis, Engines of Logic: Mathematicians and the Origin of the Computer). $\endgroup$ – vzn May 6 '15 at 18:46
  • $\begingroup$ The question was pretty clear in this regard: "an area that is of interest in pure math on it's own without considering the applications to CS." This is certainly true of many, if not most, of the mathematical questions arising in GCT. $\endgroup$ – Joshua Grochow May 6 '15 at 21:06
  • $\begingroup$ heres another similar ref re undecidability in group theory & word problems. TURING MACHINES TO WORD PROBLEMS / Miller $\endgroup$ – vzn May 7 '15 at 1:20
7
$\begingroup$

Modern research in automata theory (in a broad sense) is an interesting case. It relies on a lot of mathematics, but not necessarily the kind of mathematics you would learn in standard courses in mathematics. A very loose explanation might be that in computer science, the fundamental object is the Boolean semiring $\mathbb{B}$, while in mathematics, finite fields, including $\mathbb{F}_2$, play a prominent role.

For instance, one makes use of semigroups (also groups also play an important role) and a lot of results on finite semigroups in the recent years were originally motivated by automata theory. Semirings are also used (rather than rings): for instance, the tropical semiring was first introduced in automata theory before being used in tropical geometry, a successful new area in mathematics. Other topics related to automata include logic and finite model theory (think of Rabin's tree theorem), topology, duality and (quasi)-uniform spaces and some number theory (notably for questions dealing with numeration systems and formal power series), probability theory (notably Markov chains) and game theory.

$\endgroup$
  • $\begingroup$ The statement "the fundamental object is the Boolean semiring $\mathbb{B}$" is intriguing, but is it true? Isn't the fundamental object $\mathbb{B}^*$, i.e. strings of booleans? That's what computer science codes everything into, see also this discussion where strings of booleans are deemed to be one of the big ideas in complexity theory. $\endgroup$ – Martin Berger May 6 '15 at 7:02
7
$\begingroup$

To say a bit more about Geometric Complexity Theory (GCT): this is the application of algebraic geometry and representation theory towards a long-term program to resolve P versus NP. The questions raised in GCT tend to be deep mathematical questions, some of which go back over 100 years to the pioneers of algebraic geometry and representation theory - seemingly having nothing to do with computation, but via GCT one sees that they are in fact intimately related with computational complexity - and others of which raise new questions and ideas in pure mathematics (again, algebraic geometry and representation theory).

$\endgroup$
4
$\begingroup$

Not totally a theoretical CS topic but uses many results from theoretical CS : you may be interested in software verification which goal is to ensure that a program do what it's supposed to do, and nothing else. Among the different techniques in that topic, some are particularly math-oriented. Many critical systems, in avionics/spatial/nuclear notably, have been proved that way to ensure they are bug free.

Many mathematical fields are involved : logic, proof theory, automata theory, set theory, ...

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.