OpenAI just released this on Github. It seems like the rumors of the Unique Games Conjecture and RL = L were indeed true. There's also a lot of other stuff in there which i haven't looked at yet.
Regardless of one's views on AI, it's safe to say TCS is truly facing a watershed moment...
A new preprint claims to have proven the Komlós conjecture, a major problem in discrepancy theory and algorithms research, with the proof reportedly discovered by an AI research agent called Odin. The proof appears to be existential rather than constructive.
The problem is quite easy to explain. Quanta wrote an article about other recent progress on it very recently.
Incidentally, I was having lunch with theory faculty including Aleksandar Nikolov right when this dropped. He had just started getting a flood of emails from colleagues about the claimed proof. It felt pretty surreal seeing this in real time.
Obviously it is not peer-reviewed yet, but if results like this become routine what do we think is the fate of TCS and algorithms research(ers)?
Hi all, wanted to get some thoughts on AI related things. I know it's a polarizing topic:
We’ve had a noticeable number of blatant, poorly written AI slop “papers” recently. At the moment there is isn’t much activity over here so it’s possible to check them manually (and use feedback from comments). But I don’t really want the mods manually vetting every such post should there be an overwhelmingly large number of these submissions in the future.
Some subreddits only allow arXiv submissions and peer-reviewed papers. I for one am hesitant to do that here since I don’t want to restrict the dissemination of genuine work, even if it’s just on GitHub say.
AI is already producing STOC/FOCS level results, so ‘AI was used’ on its own should not be disqualifying. But of course, it should not come at the expense of the quality of the submission.
Would people here be interested in a recurring AI megathread, similar to r/math’s, focused on algorithms and TCS? This could maybe include how people are using AI in research or work, AI-assisted results, a discussion about its impact on the field etc.
Thoughts, comments, concerns?
Best,
Phytor & the r/algorithms Mod Team
This is a scam FYI if it wasn't obvious already. So much for 3 duo prompts a day.
This recurring thread will be for general discussion on whatever algorithm-related projects, problems, or topics you have been or will be working on this week. This can be anything, including:
* theoretical computer science and algorithm design,
* books, papers, or articles you are reading,
* coursework or self-study (what you have been learning recently),
* competitive programming or interview prep,
* preparing a talk, presentation, or project demo.
All backgrounds and levels of experience are welcome!
When I was first learning LP in undergrad (simplex, relaxations for Integer Problems, weak and strong duality and all that jazz), I honestly didn't see where it would be that useful. Now in my research it shows up quite a bit via primal-dual algorithms. These simultaneously keep track of the primal and dual solutions.
To be fair, even in undergrad one usually learns about using LP relaxations and (deterministic or randomized) rounding to get approximation algorithms for problems such as MAXSAT or Set Cover.
I'm curious where else people run into it. Has LP ever popped up in your own research or work?
Inspired by the recurring threads on r/math, we are starting our own weekly discussion thread!
This recurring thread will be for general discussion on whatever algorithm-related projects, problems, or topics you have been or will be working on this week. This can be anything, including:
* theoretical computer science and algorithm design,
* books, papers, or articles you are reading,
* coursework or self-study (what you have been learning recently),
* competitive programming or interview prep,
* preparing a talk, presentation, or project demo.
All backgrounds and levels of experience are welcomed!
Following up on the suggestion to survey the community, please pick the option that best describes you. Feel free to elaborate in the comments.
Hi all,
We're writing to share what's been happening with the subreddit and where we're headed.
A few months ago, this subreddit suffered a significant spam attack, leading to the Reddit admins restricting access and removing the previous inactive moderation team. Very recently, ownership was transferred to me. I've since recruited some mods, and we intend to clean this place up and keep it running well. For context, I'm a fledgling researcher in theoretical computer science.
To me, it's surprising how the sub stayed functional for this long. We currently have no clear rules, no post flairs, an outdated sidebar, and no resources like an FAQ or recommended textbook/reading list etc. A lot of work needs to be done here.
We have 130k+ members here, and some need decisions to be made about our direction:
Who are we building this community for? Our sub includes the following, and more:
Drop your thoughts below.
Thanks for your time, and we look forward to rebuilding this subreddit.
Best,
Phytor & the r/algorithms Mod Team
Have been seeing these geese honking around near campus for a couple of days. Took a pic this morning. It’s like they’re trying to claim territory idk lol