7
$\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?

New contributor
Robert is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$
  • 8
    $\begingroup$ Can we (as a community) just stop using these completely unhelpful terms, please? $\endgroup$ – David Richerby Jul 12 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 at 20:11
  • $\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 at 7:37
  • $\begingroup$ @DavidRicherby How about Theory A and Theory $\alpha$? $\endgroup$ – Robert Furber Jul 13 at 9:21
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.

$\endgroup$
5
$\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.

$\endgroup$
1
$\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.

$\endgroup$
  • $\begingroup$ Though perhaps someone more knowledgable in the area could add more references, like @AndrejBauer? $\endgroup$ – Joshua Grochow yesterday
  • $\begingroup$ Or @NeelKrishnaswami? $\endgroup$ – Joshua Grochow yesterday

Your Answer

Robert is a new contributor. Be nice, and check out our Code of Conduct.

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.