Here is the mini course's link, Which is about the computational lens of the physics, biology, and even Math. Eventhough it is organized by a Harvard grad student, Astonishingly the course is open for non-Harvard students and is accessible for the lay audience.

If possible, Share with us why do you wish to join the course, your learning expectations, and how do you wish to contribute to others?

Please share the announcement with everyone.

I have just discovered a magazine by European Association of TCS. It features surveys, tutorials, open problems, technical articles, and reports.

I also found other general math magazines like AMS Bulletin, AMS Notices, and EMS magazine. I was struck how uncommon those magazines are (at least for me), Especially they are all open-access unlike MAA magazine.

I had always wanted to

• Explore the literature, new areas of mathematics, and breakthroughs in research, but through an accessible source; and

• Learn more about the scientific community like opinions on education or how the field is progressing

These magazines seem to fulfill this gap, Especially they balance technical rigour, between popular science media and technical papers.

So,

• Do you think math magazines are rarely picked-up by students? If yes, Why?

• Are there student-led clubs which discuss these magazines and contribute to it?

• Do you personally follow-up one of of these magazines? If yes, What did you learn and how did they influence your career?

• Would you be interested in joining an online group for these magazines? Collaboratively, Tackling open problems, Presenting technical surveys, and Discussing social issues.

You don't need to answer all these questions.

here is the link of the lectures. As mentioned by ICM in their main page, "Lectures will be published in the ICM proceedings and freely available online".

The line up of other lectures series is very fascinating, including logic, Combinatorics, and statistics, The likes of which are no less relevant to a computer science theorist. Check them out from here.

here is an announcement of a free online summer school for introducing theoretical CS for undergraduate students.

Discuss with us,

• How to foster networking in TCS for students across the globe, Especially for under-represented minorities?

• How to make TCS more accessible for undergrad and even the general public?

• What is the best logistic way to organize such online schools?

• What are your expectations and what do you aspire to see from such online schools?

I am a software engineer and I am interested in the nature of computation. I want to initiate a study group for studying the "Philosophy and Theoretical Computer Science" course by Scott Aaronson on MIT's site(https://stellar.mit.edu/S/course/6/fa11/6.893/index.html). It has some book recommendations and research papers which are all linked in the course material section and the only prerequisite is either analytic philosophy or Computability and complexity theory. I had taken Theory of Computation course during my university days but since it has been some time so I was thinking of taking Michael Sipser's Course on it which is on OCW(https://ocw.mit.edu/courses/18-404j-theory-of-computation-fall-2020/). It has all the resources. If anyone is interested in studying with me it would be great.

Hello, last year undergraduate CS student. I think l want to do graduate studies in TCS. My favourite topics are random graph / matrix theory, sub-linear algorithms, and complexity theory.

Micheal Sipser's *Introduction to the ToC*, is one of my favourite books that I have studied and used. I understand it quite well (partly because it is well written) but I am having difficulties understanding the first chapter of *Turing Computability* by Robert I. Soare.

I am attempting to read *Turing Computability* because I have a class that covers the Arithmetic Hierarchy, and Computably Enumerable sets, and I don't understand them very well.

1. Can you point me to any resources that cover these topics in a bit more of an accessible manner?

2. What's the difference between ToC and Turing Computability. Both seem to stem from the definition from the Turing machine so I expected the content to be the same but they are very different.

Thank you.

Hello,

Links

• ACM A.M. Turing Award Honors Avi Wigderson for Foundational Contributions to the Theory of Computation

• TOC: A Scientific Perspective. 1996

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?

Here is a new curated list of theoretical computer science references. We greatly appreciate your contributions to it.

Feel free to share us your inquiries, suggestions, and feedback.

Greetings, I have just seen Boaz Barak's post on FOCS' new conjectures track. Quoting from his post:

Papers submitted to the Conjectures Track should be focused on one or more conjectures, describe evidence for and against them, and motivate them through potential implications. We are particularly excited about this as an opportunity for researchers who have been working on a very hard fundamental problem for a long time, and have identified a conjecture (or family of conjectures) that, if proven, could help resolve the problem.

FOCS is the most prestigious conference avenue in Europe for Theoretical CS, by the well-known IEEE association.

Discussion.

• What do you think was the problem in research, which motivated the creation of this new conjectures track?

• Do you agree researchers should pay more attention to conceptual ideas and conjectures, rather than doable incremental results? Why? Why not?

• Do you see this new track, As a potential for disruptive research? Do you see it a more healthy endeavor?

• Do you think this new track, shall incentivize researchers to perceive conjectures as a viable progress?

• If the idea of conjecturing as a progress spread more among the community, What kind of implications do you expect to see?

You don't need to answer all these questions. They are only meant to shed new lights on possible discussions. Feel free to comment generally, Even if not relevant to the questions above.

Best,

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?

Hello everyone,

A study group based on MIT's Mathematics for Computer Science course is going to be formed. The focus is on collaboratively solving problems not reading definitions.

People coming from various backgrounds and of different skills is encouraged. If you are good at something, You can guide someone. If you are bad at something, You can ask for help. We learn well when we struggle to solve problems, and best when we are on the right direction. Everyone is unique and can contribute in someway.

Inspired by Poly projects and open notebooks initiatives, The group's study progress is going to be publicly available, welcoming outsiders occasional contributions as well.

The group is going to be live on gitlab as it provides LaTeX support out of the box.

If you wish to join, shoot me a direct message with your email. Feel free to ask any question or even add your suggestions.

Update: The study group is live here. Anyone is still welcome to join and even meet other participants.

Hello,

I am planning to start studying computational complexity theory. As the field is technical for a fresh undergrad alumni like me, I thought a good approach is to tackle it through areas I am more familiar with.

I read Sipser's and saw couple of lectures and conferences workshops; Barak's book seems to endorse intuitive proofs; Other books are very technical for me.

While I am already building up my math toolboxes, it seems a good idea to enter computational complexity theory early even if my contribution is a very special case.

Particularly, I thought of studying notable concrete problems, alongside related math techniques and algorithms. For example SAT and its solvers. Training on reductions should also be an accessible entry for establishing relationships between different complexity classes. Defining a genre of problems by a common theme or property among them might be a good training also. Du & Ko's book and Erik's lower bounds course are my choice so far.

Do you have any feedback or comments? Do you think I am on right pathway? Do you have alternative approaches?

P.S. Send me a direct message if you wish to join me self-studying, Even if your interest is in general TCS.

This work will be verified and shepherded by a group led by Russell Impagliazzo (UC San Diego), Ramamohan Paturi (UC San Diego), and Ryan Williams (MIT). All three are experts in algorithm design and complexity theory.

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!

Hello,

No Analysis MOOC. I wanted to study Analysis akin to Rudin's Intro; I searched for many MOOCs websites, but totally found no analysis course! I am astounded as this course is mandatory and is supposed to be requested by many students.

Why? As an explanation, Maybe MOOCs websites are for-profit or targeted for audience who is less matured in abstract rigorous math, who in turn do not rely on reading careful proofs from textbooks. Thus, There's no business motivation for MOOCs to offer courses which are not going to be bought or seen by many students. Open-accessed university lecture notes and problem-sets are more likely to be pursued by students of pure-math majors.

Other than Analysis. Quickly searching through MOOCs yields courses close to the level of "Honors University Courses" of math/logic are not found. I suspect MOOCs intentionally offer easier courses, For commercial purposes. Check out for instance the syllabus of Computability, Complexity & Algorithms.

Discussion

• Are you aware of any MOOC which offers rigorous math courses?

• Why do you think pure-math students are not inclined to use MOOCs?

• How far do you agree MOOCs intentionally downgrade courses difficulty level?

Besides the questions listed above, Feel to share with us a more general comment.

Best,

update: The talk has ended, and you can see it recorded here

I am giving a talk tomorrow, 8 Apr, at 8:00 AM (UTC). Bo Li, All his PhD students, and other enthusiastic students will be joining us. It will be a very gentle intro to theoretical CS, and we will have an interactive discussion. You can even ask for general research advice.

Title A Hobbyist's Dialogue on Theoretical CS and Overview of Computational Complexity

Abstract If people thought of something fascinating about computers, Then it would usually be about some fancy practical application. In this talk we tackle computers, but their theory or pure-math perspective. A central goal is to show everyone that theory developments are no less exciting and fascinating than practical computing. We hope to expose attendees to wear different shoes for theoretical CS. Particularly, We give an overview of computational complexity theory, which deals with classes of computational problems as a whole, not concrete individual problems like algorithms. The talk assumes no technical background, and is composed mainly of historical developments. The speaker is an undergrad student, and he is in no way an expert or authorized in this field. Rather, We give more personal reflections and hope for the talk to be as interactive as possible.

Zoom Link: Here

ID: 994 9984 1826

Passcode: 941108

If you have any inquiry or feedback, Please share it with us.

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.

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

After posting this in r/csmajors, i found this sub and think, there might be more people here, who could answer this. In any case, it won't harm. So anyways, here is the original post:

Hi everyone,

i just finished my bachelor's degree in mathematics (in Vienna, Austria, Europe) and will start my master's in october, also in Vienna. During my bachelor's degree, i found, that i enjoy theoretical CS and in particular formal language theory and (algebraic) automata theory. My master's will be in 'Logic & Computation' and I plan to do a lot of theoretical CS courses. However, the supervisor of my bachelor-thesis told me that there is hardly any research in the field of formal language theory in Vienna. Therefore, i cannot do a lot of courses in this area in Vienna and if plan to do a PhD in this field it will most likely not be possible in Vienna. Therefore, i wanted to ask if any of you know any places, where there is a more reasearch in this field. This would be interesting for a potential semester abroad or if I decided to do a PhD. Of course, I would prefer places in Europe, but any input is appreciated. My supervisor told me, there is some research in this area in France (Pin is sadly retiring) and in Stuttgart, Germany. However, the researchers i contacted don't really reply in a timely manner and I would like to contact several ones, to have the best chances of finding something.

I have been getting into TCS recently and on first glance it seems like PvsNP is the only problem people cares about. Is that true ? Is there other research being done that is not related or not similar to PvsNP?