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?

Springer link (should be free to download with an institutional account): https://link.springer.com/book/10.1007/978-3-642-24508-4.

I'm recently trying to work my way through Stasys's Boolean Function Complexity, and this book seems so well-written (at least content-wise based on my scan of what it covers)! I'm trying to type set a solution manual for this book, since it is still missing (not aiming for it to be complete or perfectly accurate in any foreseeable future. Just want to get started on a good reference for a broader audience as the topics in the book can be lofty at times).

If there are enough interests, I'll create a discord or slack for people interested and share it here.

Hello,
I wanted to gauge the collective mind on the following conundrum. I want to apply for a research - based masters prepping for a PhD. My main interest is in computational Ramsey Theory and Algorithmic Game theory. It seems that I can do both in either Math or CS departments.

I realize that any program in a good school would be fairly competitive. However I am wondering if I would be putting myself at a disadvantage applying for MSCS as I will be competing with all the people aiming for AI/ML , systems etc.

Or would the larger cohort (I am speculating here), compensate for this (or perhaps my reasoning is flawed and with MS/MA Math, I'd be competing with all the analysis and geometry people haha). (Also, I know that there there is direct to PhD pathway, but my questions is here is rather specific to Masters).

Many thanks !

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 know STOC/FOCS/SODA are top tier and have some idea of how ICALP, APPROX, ALGO, IPCO rank but beyond that I really don't know

https://cstheory.stackexchange.com/questions/7900/list-of-tcs-conferences-and-workshops

Hello there!

Today we will be diving into one of the most common ways of representing data and modeling problems (and solutions) in Computer Science. We will be talking about Graphs.

This is the third of a series of posts introducing graph theory in a very visual way.

Now that we know some basic definitions of graph theory, it is time to see how graphs can be represented in a program. We will explore the most common representations and analyze their pros and cons.

At the end of the post, you will find some algorithmic challenges so you can try and apply some of the topics that I will explain today. Feel free to skip to that part if you think you already have the necessary skills to solve them.

Have a nice read!

Algorithmically Speaking - #5: Representing Graphs

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?

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,

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?

Hi Everyone, I wanted to ask if there are recommendations for TCS master's programs in the US. I have a list of European programs that I want to apply to, but I have no idea what my chances are (the MPRI program looks very appealing)

Background: I am an international student studying at a top 20 US college. I major in math with a CS minor (DS, Algorithm, Number Theory, Logic, Combinatorics), and my capstone is related to logic/formal methods, which might get published next yr. My GPA is 3.62 (which is not high) and my GRE is 330.

I am looking for a program that introduces me to different areas of TCS and I would like to pursue a Ph.D. afterward.

For the US, I am mainly looking at master's programs at Brown, Columbia, NYU Courant, etc. But these programs seem to mainly focus on theory A, so I am not sure they are a good fit for me.

Thank you so much in advance!

Hello,

Supportive Community. Students are typically affiliated with institutes where they are around a supportive community. In case they struggled with a course problem or even a research agenda, Some mentor or a friend is likely to provide hints and support. Definitely such discussions are vital to their mathematical progress. Even professional researchers do collaborate with each other.

Solo Students. Unfortunately it is not always the case that a student can find others who support. I see three scenarios, in case she failed to solve a course problem:

• (si) Seeing the final complete solutions of the problem she struggled with. For example, By the instructor's manual or some community.
• (sii) Keeping a journal of partial progress, in hope to revisit and solve them later.
• (siii) Being satisfied for wrestling with the problem, without any intentions for solving it later.

Commentary.

• (si) I am too wary would miss a student the central goal of polishing her own skill of solving a problem. I personally do not see any value from seeing a final complete solution.
• (sii) Seems the typical approach for a student to polish her own taste but I am too wary it would unproductive, Consuming much time only to complete a basic course.
• (siii) I am too wary a student won't be able to certify herself to have had completed a course. So it won't count as a progress.

Solo Researchers. A similar argument can be made for researchers who struggle with a research investigation, for which they cannot find a supportive community.

• (ri) Give-up on their unique research, and follow the majority of the community, where they can receive support.
• (rii) Persist.

Discussion.

• What is your feedback on my commentary?
• What is your recommended strategy for solo students? How can they progress in a productive manner?
• Do you think it is a wise decision to only study a course in case a student finds a supportive community?

My post is more inclined towards solo students but you can still comment on solo researchers part. Feel free to comment generally outside points listed.

Sincerely,

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,

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,

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.

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?

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.

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.

So I've been reading Sipser's theory of computation book, and I've come across the pumping lemma for context-free languages, which as a reminder says that if a language is context-free, then there is some length p such that all strings longer than p can be represented in the form

s = uv^i x y^i z

and be pumped and remain in the language.

He then goes on to show that the languages a^n b^n c^n, as well as a^i b^j c^k (for i <= j <= k) are both not context-free, using the pumping lemma.

While the proofs for both are just casework, to me the conceptual point here is that if your language relies on some kind of global structure in its description, then it's very unlikely to be context-free (since CFGs are just applying rules locally).

Is there some way to formalize this idea?

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.

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.

Hello, I have just learned about prof. Ryan's YouTube channel and Discord community, Which centers around theory of computation. At the moment of writing these lines his Discord community has 400+ members! We invite everyone to join, Suggest new ideas, and even volunteer.

See his YouTube and his Discord.

My proving skills in CS is poor. For eg- proving things by induction etc. I want to learn more about proving techniques and practice them. Is there a resource/ textbook anyone can point me towards?

Or

Some proofs that i have seen were from automata theory and graphs. I was thinking to go through ullmann's automata book and rosen' discrete book ( graphs). It may have proving techniques and exercises for me to practice on. Am i in the right direction?