<p>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 <a href="http://www.ams.jhu.edu/~abasu9/RFG/pivotexponential.pdf" rel="noreferrer">Friedmann, Hansen, and Zwick</a>. 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. </p>

CC BY-SA 4.0
2019-07-12T14:33:16.630Z
2019-07-12T14:33:16.630Z
Sasho Nikolov
<p>One example (from my research field) is analysis of dynamical systems: in a (linear) dynamical system, you are given a matrix <span class="math-container">$A\in {\mathbb Q}^{d\times d}$</span> and you reason about various properties of <span class="math-container">$A^n$</span>. For example, the <em>Kannan-Lipton Orbit Problem</em> asks, given two vectors <span class="math-container">$s,t\in \mathbb Q^d$</span>, whether there exists <span class="math-container">$n$</span> such that <span class="math-container">$A^ns=t$</span>.</p>

<p>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. </p>

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

<p>A good place to start reading on these is <a href="https://dl.acm.org/citation.cfm?id=2857050" rel="noreferrer">here</a>.</p>

CC BY-SA 4.0
2019-07-12T15:39:23.907Z
2019-07-12T17:49:27.193Z
2019-07-12T17:49:27.193Z
Shaull
<p>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 <a href="https://doi.org/10.1007/BF01201998" rel="nofollow noreferrer">Bellantoni &amp; Cook</a>. More recently, the work of <a href="http://www.cs.unibo.it/~dallago/research.html" rel="nofollow noreferrer">Ugo Dal Lago</a> comes to mind.</p>

CC BY-SA 4.0
2019-07-16T16:46:39.593Z
Though perhaps someone more knowledgable in the area could add more references, like @AndrejBauer?
Joshua Grochow
CC BY-SA 4.0
2019-07-16T16:46:46.917Z
Or @NeelKrishnaswami?
Joshua Grochow
CC BY-SA 4.0
2019-07-16T16:46:23.323Z
2019-07-16T16:46:23.323Z
Joshua Grochow
<p>In the following two questions <a href="https://cstheory.stackexchange.com/q/1521/53307">Origins and applications of Theory A vs Theory B?</a> and <a href="https://cstheory.stackexchange.com/questions/944/solid-applications-of-category-theory-in-tcs">Solid applications of category theory in TCS?</a>, many people shared their knowledge and opinions about the division of those two areas in theoretical CS.</p>

<p>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?</p>

CC BY-SA 4.0
2019-07-12T19:10:27.630Z
Can we (as a community) just stop using these completely unhelpful terms, please?
David Richerby
CC BY-SA 4.0
2019-07-12T20:11:36.137Z
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.
Sasho Nikolov
CC BY-SA 4.0
2019-07-13T07:37:51.897Z
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.
Bruno
CC BY-SA 4.0
2019-07-13T09:21:34.903Z
@DavidRicherby How about Theory A and Theory $\alpha$?
Robert Furber
<terminology><ho.history-overview><research-practice>
Are there any intersections between Theory A and Theory B?
Robert
# Are there any intersections between Theory A and Theory B?

(Asked by: username_0 on 2019-07-12)

In the following two questions [Origins and applications of Theory A vs Theory B?](https://cstheory.stackexchange.com/q/1521/53307) and [Solid applications of category theory in TCS?](https://cstheory.stackexchange.com/questions/944/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?

**Tags:** terminology, ho.history-overview, research-practice

> **Comments:**
> **username_1**: Can we (as a community) just stop using these completely unhelpful terms, please?  
> **username_2**: 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.  
> **username_3**: 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.  
> **username_4**: @DavidRicherby How about Theory A and Theory $\alpha$?  

---

## 3 answers

### Answer by username_2 on 2019-07-12. Score: 7

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](http://www.ams.jhu.edu/~abasu9/RFG/pivotexponential.pdf). 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.


---

### Answer by username_5 on 2019-07-12. Score: 7

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](https://dl.acm.org/citation.cfm?id=2857050).


---

### Answer by username_6 on 2019-07-16. Score: 2

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](https://doi.org/10.1007/BF01201998). More recently, the work of [Ugo Dal Lago](http://www.cs.unibo.it/~dallago/research.html) comes to mind.

> **Comments:**
> **username_6**: Though perhaps someone more knowledgable in the area could add more references, like @AndrejBauer?  
> **username_6**: Or @NeelKrishnaswami?  

---

