r/theoreticalcs • • Feb 18 '25

Can Relativity Affect Computability and Complexity

0 Upvotes

Hi all, I've been pondering the behavior of computational complexity and computability in a relativistic environment, and I'd appreciate hearing people's thoughts from CS, math, and physics.

In traditional theory, we have a universal clock for time complexity. However, relativity informs us that time is not absolute—it varies with gravity and speed. So what does computation look like in other frames of reference?

Here are two key questions I’m trying to explore:

1️ Does time dilation affect undecidability?

The Halting Problem states that no algorithm can decide whether an arbitrary Turing Machine halts.

But if time flows differently in different frames, could a problem be undecidable in one frame but decidable in another?

2️ Should complexity classes depend on time?

If a computer is within a very strong gravitational field where time passes more slowly, does it remain in the same complexity class?

Would it be possible to have something like P(t), NP(t), PSPACE(t) where complexity varies with the factor of time distortion?

Would be great to hear if it makes sense, has been considered before, or if I am missing something essential. Any counter-arguments or references would be greatly appreciated


r/theoreticalcs • • Dec 24 '25

Discussion The Future of Algorithms: Ideas will Matter more than Compute

2 Upvotes

Link: The Future of Graph Algorithms: Ideas will Matter more than Compute

TLDR

As hardware scaling approaches a ceiling, algorithmic ideas will become an essential alternative to “more compute.” Faster, simpler, and principled algorithms, paired with strong incentives for high-quality datasets, may define the next phase of progress.

Discussion.

  • Do you think there is still promising progress by hardware or dataset scaling?

  • Do you see current theory progress promising for the future of practice?

  • If theory is shaping tomorrow, how do you see it will happen?


r/theoreticalcs • • Apr 18 '26

Is Integrated PHD in theoritical computer science from Imsc chennai worth?

5 Upvotes

Imsc(Institute of mathematical sciences) in chennai admits students into their integrated phd programme in TCS(Theoritical computer science) through JEST exam.

I am fascinated by theoritical computer science and appeared for JEST 2026 and it went well(Results are yet to be declared)

My question:

(1)Does doing a PHD in theoritical computer science worth it from Imsc chennai?

(2)What are the careers we could pursue after that?

My qualifications are Btech.


r/theoreticalcs • • May 31 '26

Discussion Is Theoretical CS facing a crisis similar to Particle Physics?

9 Upvotes

Link: Is Particle Physics Dead, Dying, or Just Hard?

Quote:

without a way to search for heavier particles, the field would undergo a slow decay.

Summary. Particle physics had no notable progress for the past decade which raises concerns about its worthiness.

Pragmatic CS is moving very fast, and classical theoretical CS like worst-case analysis became less relevant. That is what has motivated Tim to author his book, suggesting new directions. Recently Simons Institute hosted The Role of TCS in Modern Machine Learning.

Personal Opinion. I think TCS should be relevant to CS in the same way Theoretical Physics is relevant to Experimental Physics. CS Theorists may envision theories distant from applications but they should see a path relevant to practice.

Discussion. Do you think it is healthy for TCS to be driven by the pragmatic successes of CS? Do you think it is healthy to think of TCS as a subfield of Pure Math? Do you see lessons from Particle Physics for the CS Theory community?


r/theoreticalcs • • Feb 24 '25

You can prove Kolmogorov complexity with a zero-knowledge proof

10 Upvotes

I'm not sure if I'm the first person to point this out, but enumerating all strings<=len(string) constitutes a zero-knowledge proof of Kolmogorov complexity because the proof is "said" but the verifier has no way to retrieve it. The verifier can guarantee the proof is said if the enumeration is truly done. In most zero-knowlege proofs, the prover knows the proof, but in some neither the prover nor verifier knows the proof. There is an existing paper on a zero-knowlege proof relating to Kolmogorov complexity but it is a statistical ZKP, this is a perfect ZKP. Would love to start a discussion and know other's thoughts on the implications of this idea


r/theoreticalcs • • May 18 '22

Question Is it wise to pursue math not endorsed by the community? Reflections on Leslie Lamport's Program Model Checking

10 Upvotes

Article Link

Leslie Lamport. A Turing award laureate (alike a Fields medalist but in computer science) who contributed fundamental algorithms in the field of distributed computing. Currently he is developing TLA+, An environment that enables developers to model their software on a higher conceptual level, For checking design issues. Eventhough the industry is totally refusing his approach, He is still motivated to pursue his work.

Quote.

Well, I’m doing what I can. But basically, programmers and many (if not most) computer scientists are terrified by math. So that’s a tough sell.

Discussion.

  • Do you think it's wise to pursue a math research agenda, targeted for a community refusing it?

  • Do you personally think software engineering and logic techniques, should go hand-in-hand? Why? Is it possible? How?

  • Do you think the effort devoted by Leslie in model checking or program verification, Might benefit new discoveries in the future, which are not thought of nowadays?

Feel free to comment generally, Even if not related to questions listed above. General comments even if not related to Leslie's case are welcomed also.


r/theoreticalcs • • Nov 21 '22

Discussion "What you learn from others you can use to follow. What you learn for yourself you can use to lead" by Hamming

Thumbnail self.math
3 Upvotes

r/theoreticalcs • • Aug 04 '25

Discussion Springer Publishes P ≠ NP

Thumbnail
reddit.com
5 Upvotes

r/theoreticalcs • • Nov 21 '22

Discussion Mathstodon, A Twitter alternative for mathematicians

9 Upvotes

Link: Mathstodon

Background. After Elon Musk's acquisition of Twitter, many had backlashed on his decisions shaping the platform's future. Mastodon, A Twitter alternative is gaining popularity more than ever now.

Decentralization Philosophy. Mastodon is designed to be decentralized. There are multiple servers, each with a different administrator. If a user disagreed with a server's rules, she can easily transfer to another server whose maintainer she agrees with. The point is social media is meant to empower the community and hence no single authority should be in complete control of it.

Discussion.

  • What didn't you like in mainstream social media, or public freedom of speech generally?

  • How do you think mathematicians/students should express their ideas and opinions?

  • Do you see potential in the community, adopting new methods of communication?


r/theoreticalcs • • Apr 16 '22

New Horizons in Theoretical Computer Science 2022, Online Summer School

10 Upvotes

Here is the website with link for applying.

Share with us:

  • What do you like the most about online summer schools?

  • What do you wish to see in them for improvement?

  • Whether you had experienced an online school, and how did it impact you?


r/theoreticalcs • • Apr 24 '25

Looking for theoretical CS problems with a strong mathematical aspect (college sophomore level)

11 Upvotes

Hi everyone,

Lately I’ve been on the hunt for interesting theoretical computer science problems or algorithmic ideas to explore on my own, but I’ve been struggling to find the right resources. I’ve checked a few university libraries near me, but most of what I find is very "practical" CS — programming languages, software engineering, systems, etc.

What I’m really after are problems that sit closer to the mathematical side of computer science — the kind of questions that involve elegant combinatorics, logic, graph theory, or automata. Think of things like “stack-sortable permutations" the kind of problem Etienne Ghys touches on in A Singular Mathematical Promenade.

I’m roughly at the level of a second-year undergraduate in computer science or math in the US system (discrete math, linear algebra, and basic algorithmic thinking). I’d love any book recommendations, problem collections, lecture notes, or even just interesting problems you think fit this vibe.

Thanks a lot in advance!


r/theoreticalcs • • Apr 10 '24

Discussion Avi Wigderson wins the Turing Award. Remembering his 1996 essay

17 Upvotes

Hello,

Links

Omer Reingold:

During my studies (ages ago), I was intensely attracted to TOC. But at the same time, I felt that the field is under constant external attack. It was claimed that we are not as deep as Math and not as useful as CS.

Discussion. Given that Avi has won both the Turing award, and Abel prize with László Lovász, What kind of lessons would you advise younger generations, in light of Omer's quote?


r/theoreticalcs • • Jul 19 '25

CS Theory vs Math (or both)

Thumbnail reddit.com
3 Upvotes

r/theoreticalcs • • Mar 02 '25

Can Processing Power Be "Catalytic" Like Memory?

10 Upvotes

I've recently learned about catalytic computation, where you can solve problems with minimal dedicated space by borrowing memory that must be returned intact afterwards. Interestingly, having catalytic space expands the class of problems that can be solved efficiently.

This led me to wonder: Could a similar concept be applied to processing power?

Specifically: Can we solve k^n instances of an NP-complete problem in O((k^n)·(n^c)) total time by strategically reusing computation across instances? (where k and c are fixed)

While this would achieve polynomial average time per instance, this wouldn't prove P=NP since the total runtime remains exponential. However, an approach like this seems relevant for practical computing - especially in machine learning where systems repeatedly solve similar hard problems and might learn their structure over time.

Has anyone encountered research in this direction? Are there theoretical frameworks or known limitations for this kind of computation reuse? Any relevant papers or terminology would be much appreciated.


r/theoreticalcs • • Jun 27 '25

Galois roots instead of binary

4 Upvotes

I’ve been interested with two maybe disjoint things, Felix Klein and the use of icosahedral symmetry, and graphene. I’m wondering if it’s possible to use Galois permutations as the basis of a kind of Boolean logic? Where roots would correspond to distinct resistive values in graphene that when twisted to different angles, be it Mott insulation or ballistic transport, represent roots of the solvable quintics. What makes graphene unique is that it’s possible to twist the lattice in such a way the resistive value of the material follow a gradient. Is computer logics only requirement that the resistive states are deterministic and repeatable for a transistor to represent a math framework?


r/theoreticalcs • • Apr 11 '25

Discussion How do PCP systems interact with oracles?

3 Upvotes

A PCP(r(n), q(n)) system is a probabilistically checkable proof system. These systems (as I understand them) are verifiers that:

  1. Generate r(n) random bits.

  2. Perform some computation to decide which q(n) bits to query from the proof (possibly using the random bits from the previous step).

  3. Query q(n) bits from the proof. The system is non-adaptive so it must make all the queries before receiving any of the answers to a query.

  4. Perform some computation to decide whether to accept or reject.

  5. The verifier accepts or rejects and it is allowed to incorrectly reject with probability at most 1/2 (as I understand it, a different constant could be used, but 1/2 is the most common).

Also, steps 2 and 4 must be done in polynomial time, since the verifier is a polynomial time Turing machine (with some augmentations).

My question is: what happens when this verifier is given access to an Oracle?

  1. The verifier can only query the Oracle during step 4.

  2. The verifier can query the Oracle during step 4 or step 2. For example, this could "help" with the choice of bits to query.


r/theoreticalcs • • 16d ago

ETH False

Thumbnail
youtube.com
6 Upvotes

Ryan O'Donnell explores the theoretical possibility that SAT can be solved in subexponential time by analyzing the Permanent of sparse matrices. The discussion details technical strategies, including matrix polynomials and Hermite interpolation, while examining how counting complexity relates to traditional computational assumptions.


r/theoreticalcs • • Jun 05 '26

Discussion What to expect when I do MSc CS Theoretical Computer Science given that I don't have strong Math background?

3 Upvotes

I am going into year 4 of BSc CS. By the time I am done I will have done this math modules:

·        Introductory Probability > Basic Statistical Theory I

·        Differential Calculus > Integral Calculus

·        Foundation of Computation > Discrete Mathematics > Formal Methods

·        Linear Algebra 1 > Linear Algebra II

This, of course, is in addition to other BSc CS such as DS&A.

I am interested in doing MSc CS, focusing on Theoretical Computer Science; particularly Computational Learning Theory. In our school, this will be a 60 credit dissertation. I would like to have opportunities to become:

·        Applied Scientist

·        AI Algorithms / R&D Scientist

I wonder if I have enough math for this path since I did not do a lot of analysis (Game Theory, Real Analysis 1 and 2, for example), and I did not do a lot of Statistics (Probability and Bayesian Inference).

I need to know how to approach this gap. I feel a little insecure and wish I had done BSc Math instead.

How likely am I to finish my MSc CS in the 2 years that it is offered, given I will also be a T.A.?

Please advise me.


r/theoreticalcs • • May 19 '26

Does anyone know where to find the supplementary materials for Arora and Barak Computational Complexity?

Thumbnail reddit.com
3 Upvotes

r/theoreticalcs • • May 02 '25

Discussion Oxford Online Math Club

14 Upvotes

Hello,

Oxford's Online Math Club had caught my interest with its high-quality content and accessibility for everyone.

Discussion

  • Would you be interested in a similar initiative but for TCS?

  • What are you looking forward to see, which is missed from your local community?

  • How do we ensure an efficient and effictive communication with members coming from various backgrounds?


r/theoreticalcs • • Jun 07 '26

Discussion Thoughts on Using LLMs for Understanding Papers?

7 Upvotes

I’m an undergraduate senior. I plan to do a PhD in TCS. Currently, I am doing research with one of my faculties. He has assigned a few papers for me.

Whenever I find something challenging, I use LLMs to clarify it to me, and it does it quite well. I asked my professor and he said he is fine with it.

I wanted to know, is it a good practice in the long run? I would love to get your thoughts. Thank you


r/theoreticalcs • • Jun 30 '26

Ryan Williams' Interview by Ryan Peterman

Thumbnail
youtube.com
8 Upvotes

r/theoreticalcs • • Jun 04 '26

Avi Wigderson Interview by Ryan Peterman

Thumbnail
youtu.be
6 Upvotes

Share with us your best moments and insights