What CS theories are absolutely paramount for someone new to TCS to understand? [closed]

First - I'm happy to be a part of this community. Electronics and software engineering are both my passion and my profession, yet I feel as if I'm missing a solid basis in theoretical computer science. This field absolutely fascinates me, and I was pleased to see a Stack Exchange community built around it. So thanks to everyone who contributes.

I'm interested in building well-rounded foundation TCS, but don't know where to start. Of course Turing, etc is very popular, but I'd like some reference from researchers in the field on what theories are critical to have a greater, well rounded understanding of computers, while actually solving real problems. Please include any examples/advice where TCS has helped you solve a specific problem, if applicable.

My questions..

• What areas are critical for me to study in mathematics?
• What areas are exciting and "hot" in theoretical CS right now?
• What areas are incredibly useful to consider for hardware innovation?
• What areas are useful when considering software innovation?

If it helps at all I work in IoT as a software/cloud architect, primarily writing ruby/C++, while occasionally working with EE on hardware design. I'm just starting to get into PCB design in my free time.

Thanks again in advance, looking forward to learning!

closed as too broad by D.W., Jeffε, Mohammad Al-Turkistany, Kaveh, David EppsteinJun 12 '17 at 0:55

Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

(Disclaimer: this answer has a focus on programming languages theory, which is only one of the many disciplines under the TCS umbrella. Apologies for the length.)

A small digression

You are asking for topics in TCS which

• are "hot" in theoretical CS right now
• are useful for innovative applications in software/hardware in the next future

From the way you pose the question, I am led to think that you believe that the two requirements above largely overlap, and/or that only bleeding edge research in TCS can have some impact in future technologies. If that is the case, I would instead argue that the overlap is instead much smaller.

First, CS theory is usually very far ahead most applications. This is not unlike theory in other science disciplines. In the past, some great theoretical developments took much time to influence the industry. A few examples:

• Turing's vision of computers influenced automatic computers
• Church's $\lambda$-calculus influenced programming languages
• Higher order functional programming influenced Google's map/reduce
• System F influenced generic types of Java (and C#, Scala, etc.)
• System F$\omega$ influenced Scala higher kinds
• Church-style encodings of algebraic data types influenced the "visitor pattern" in OOP
• Category theory influenced functional programming
• Constructive/intuitionistic logic influenced type systems

These influences did not happen overnight. If history repeats, some new technology tomorrow is more likely to draw from old-ish theory (relatively speaking) than bleeding edge discoveries.

Second, while some theoretical research is directed by some clear applications, sometimes research is driven by curiosity: when we discover a new approach and the first results appear to lead to an elegant theory, which reshapes our way of thinking about some topic, then we follow that direction. Often, even if we can't find a practical application right now, we still want to know how far we can go!

Third, some of the most powerful theory involves negative results. These, on the one hand do not tell us how to solve problems, but on the other hand tell us to avoid wasting resources trying to achieve the impossible.

For instance, computability theory tells us that we cannot precisely count the number of pages in a PostScript document (!), so we need to either move to better document formats or live with some approximate solution. Dually, we learn that if we design a new media format, we should try to avoid the same issues.

Another example: the so-called "free theorem", or parametricity property, can be used to prove the impossibility of writing a function with a certain polymorphic (or generic) type, in some languages.

Another: the Curry-Howard isomorphism can be used for a similar goal, proving the impossibility of a hypothetical program. (Shameless plug: I once used that to answer a Scala question on StackOverflow)

Some suggested "paramount" topics

(The following lists are not, by any means, complete. I only wrote the first topics that came to my mind.)

I would recommend the following topics as the bare minimum.

• [Logic] Classical propositional logic. First order logic. Naive set theory.
• [Computability] Decidable and semidecidable problems. Rice theorem. Many-one reduction.
• [Computational complexity] P vs NP. Completeness / hardness. Polynomial reduction.
• [Programming languages] $\lambda$ calculus: untyped & simply-typed. Church encodings (for untyped). Fixed points vs recursion.

These are more advanced. I would not recommend to study them all, albeit maybe one should know what these topics are about, at least. Having even a superficial understanding of these can help in keeping the mind open.

• [Logic] Intuitionistic logic. ZFC set theory. Linear logic.
• [Geometry] Basic topology.
• [Domain theory] Posets. $\omega$CPOs. Complete lattices. Scott topology. Fixed point theorems (Tarski, Kleene). Induction ($f(x)\sqsubseteq x \implies \mu f \sqsubseteq x$). Coinduction.
• [Computability] Rice-shapiro.
• [Type theory] Polymorphic types (System F). Dependent types and recursive/inductive types (Calculus of Constructions, Coq, Agda, etc.). Curry-Howard. Homotopy type theory (hot topic).
• [Category theory] Products/coproducts. Functors. Natural transformations. $F$-algebras/coalgebras.
• [Programming languages] Imperative, functional, and logic programming. Formal semantics: operational (small and big step), denotational, axiomatic (Hoare logic). Continuations.
• [Model checking] Temporal logics (modal $\mu$ calculus, CTL, LTL, etc.). SAT-solvers. SMT-solvers.
• [Concurrency] Petri nets. Process algebras.

These are even more advanced or hotter topics.

• [Programming languages] Verification. Abstract interpretation. Gradual typing.
• [Category theory] Cartesian closed categories. More "abstract nonsense" in general.
• [Model checking] SAT-solvers. SMT-solvers.
• [Type theory] Homotopy type theory (hot topic).
• So. Many. Others.

And finally,

• the topics mentioned in the digression above :-)

Most, if not all, these topics have had a deep influence on the design of modern programming languages. Some of these can also affect the way we think rather deeply. Here's a few examples from my experience.

When stuck in writing a correct while loop, one might stop and try to think about the loop invariants, and solve the issue. Of course, this only happens if one has seen Hoare logic before.

Remembering certain programming techniques can be hard. Sometimes, theory can help to quickly recall / reconstruct such techniques. For instance, above I mentioned the visitor pattern. Its definition can be recovered remembering that recursive types are interpreted as initial $F$-algebras, so by initiality, we immediately obtain an associated type $$\mu F \to \forall \alpha.\ (F\alpha \to \alpha) \to \alpha$$ So, in OOP, we would take the object (of recursive type $\mu F$), the visitor (of type $F \alpha \to \alpha$), and must return the result of the visitor ($\alpha$). Translating this into OOP, say Java, is routine.

This might look as gibberish before studying these topics, but I believe one can see that, in this way, a one-line theoretical description can summarize a complex technique like the visitor pattern.

Concluding, I hope I managed to show that the topics above have had an impact on software, and probably will have more in the future. I also hope this does not feel too overwhelming, especially since it's only about the PL part of TCS! :-)

• I marked this answer as correct because it was the most inclusive and insightful to my question. Thanks to everyone for the feedback and look forward to more discussion once I get to learning :) – iangolden Jun 11 '17 at 19:04

Here is a partial answer on "hot" areas in theoretical computer science, intended in a precisely particular order, and in no way biased towards the author's research interests.

1. Algorithmic Game Theory
2. Theoretical Machine Learning and theory of Deep Learning
3. Streaming Algorithms
4. Sum of Squares Hierarchy
5. Fine-Grain Complexity
6. Property Testing

I would start of with the textbook "Computational Complexity" by Christos H. Papadimitriou.