8
$\begingroup$

In the following two questions Origins and applications of Theory A vs Theory B? and Solid applications of category theory in TCS?, many people shared their knowledge and opinions about the division of those two areas in theoretical CS.

I am a student in mathematics with experience in both graph theory and category theory, crucial mathematical knowledge for theory A and B, respectively, and I am seeking to learn more and probably even do some serious research in theoretical CS. I am interested in whether there are any intersections between theory A and B, and if so, are there any people who have done some work in the intersections or at least are there any references in this topic?

Improve this question
$\endgroup$
4
  • 9
    $\begingroup$ Can we (as a community) just stop using these completely unhelpful terms, please? $\endgroup$
    – David Richerby
    Jul 12, 2019 at 19:10
  • 1
    $\begingroup$ Despite giving an answer, I also think the labels are not very well defined, have more sociological than scientific meaning, and are not all that helpful. $\endgroup$
    – Sasho Nikolov
    Jul 12, 2019 at 20:11
  • 1
    $\begingroup$ In the first question you link, automata are described as Theory A. I would say they were mainly Theory A in the 70's or 80's (studied as a weak model of computation), but they are now much more a Theory B subject. Or at least, they are both and can count as a natural intersection. $\endgroup$
    – Bruno
    Jul 13, 2019 at 7:37
  • 1
    $\begingroup$ @DavidRicherby How about Theory A and Theory $\alpha$? $\endgroup$
    – Robert Furber
    Jul 13, 2019 at 9:21

3 Answers 3

Reset to default
7
$\begingroup$

One cool example of work that straddles things that are typically considered theory A and things typically considered theory B are the lower bounds on the running time of the simplex algorithm with randomized pivoting rules, due to Friedmann, Hansen, and Zwick. The lower bounds rely on lower bounds for policy iteration algorithms for parity games, which are a tool used in formal verification and automata theory.

Improve this answer
$\endgroup$
6
$\begingroup$

One example (from my research field) is analysis of dynamical systems: in a (linear) dynamical system, you are given a matrix $A\in {\mathbb Q}^{d\times d}$ and you reason about various properties of $A^n$. For example, the Kannan-Lipton Orbit Problem asks, given two vectors $s,t\in \mathbb Q^d$, whether there exists $n$ such that $A^ns=t$.

These types of problems can be looked at as reachability problems for linear loops, which places them well in the domain of formal verification, SIG-LOG, and Theory B.

However, the technical analysis typically uses tools from number theory, analysis, and algebraic computations, which are more in the scope of Theory A.

A good place to start reading on these is here.

Improve this answer
$\endgroup$
2
$\begingroup$

As far as I understand it, linear logic and "implicit complexity theory" use tools that are often found in Theory B (type theory, theory of programming languages, etc.) to capture and study complexity classes. Some of this work goes back to Bellantoni & Cook. More recently, the work of Ugo Dal Lago comes to mind.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Though perhaps someone more knowledgable in the area could add more references, like @AndrejBauer? $\endgroup$
    – Joshua Grochow
    Jul 16, 2019 at 16:46
  • $\begingroup$ Or @NeelKrishnaswami? $\endgroup$
    – Joshua Grochow
    Jul 16, 2019 at 16:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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