5
$\begingroup$

I am Ph.D student (about to graduate) in TCS. I have worked on some problems. I have been able to publish few research paper. There are many research problems in mathematics as well in TCS. I am sure that all of the problems of mathematics are not interesting to all TCS researchers. There seems to be gap between mathematics and TCS to me. I have made many attempts to define research problem on very old mathematical problems, some time algorithm is trivial and some time motivation is not clear to me. I don't if in the future I come up with an algorithmic problem on some mathematical problem will that be interesting to TCS community. I am here as I want to know when it makes sense to define a algorithmic question on mathematical problem for TCS researchers point of view. Let us say I am able to give an algorithm which classify all modules(Algebraic structure) of some rank. Will that interesting to TCS researchers?

There is one other way for me to not care about other and work on problems which I find interesting, but in that case I don't I will be a successful researcher or not.

In short while defining algorithmic question what are things or questions I should ask to myself

Question : What type of mathematical problems interesting for TCS researchers?

Improve this question
$\endgroup$
2
  • $\begingroup$ An interesting problem is to prove formally that your implementation actually computes the algorithm you have in mind. For non-trivial implementations, hand-written proofs don't suffice, since the amount of detail one needs to track is too large for the conventional approach to proof (= pen + paper). You'd need to verify it in a proof assistant. $\endgroup$
    – Martin Berger
    Mar 25, 2019 at 9:44
  • 1
    $\begingroup$ Simple answer is, write down your algorithm clearly then check is it using some non-trivial tool from TCS even with some modification then you have a result. $\endgroup$
    – adc
    Mar 27, 2019 at 9:28

1 Answer 1

Reset to default
3
$\begingroup$

Let us say I am able to give an algorithm which classifies all modules (algebraic structure) of some rank. Will that be interesting to TCS researchers?

Roughly speaking...

  • It will be interesting to applied mathematicians if they find that the algorithm is fast enough in practice in some sense.

  • It will be interesting to pure mathematicians if the algorithm gives new insight into the structure of modules or lets them compute examples that can be used to test conjectures.

  • And will be interesting to TCS researchers if there are also lower bounds on how fast an algorithm for this problem can possibly be, or if this problem is related to algorithms for other problems such as classifying rings, module isomorphism etc.

An example that was interesting to all three to varying degrees is Tarski's theorem on the real field.

Improve this answer
$\endgroup$
4
  • 3
    $\begingroup$ Tarski's theorem on real closed fields actually is used in practice, if by practice you include people building proof assistants. $\endgroup$
    – Neel Krishnaswami
    Mar 23, 2019 at 21:41
  • 1
    $\begingroup$ @NeelKrishnaswami thanks I modified my statement $\endgroup$
    – Bjørn Kjos-Hanssen ♦
    Mar 24, 2019 at 3:28
  • $\begingroup$ Bjørn Kjos-Hanssen I have doubt in third point you have mentioned in the answer. Is it only the lower bound or algorithms also. $\endgroup$
    – user49003
    Apr 3, 2019 at 6:24
  • $\begingroup$ @A_Theory well if you relate your algorithm to say the AKS primality test or to Babai's work on graph isomorphism it should be of interest.... but I think I see what you mean. $\endgroup$
    – Bjørn Kjos-Hanssen ♦
    Apr 3, 2019 at 13:19

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.