Theoretical Computer Science

[Anonymous No.11605810]

What's /Sci/'s opinion on Theoretical Computer Science?

[Anonymous No.11605846]

>>11605810

I'm a PhD at one of the top schools and have taken four or five grad-level theory classes.

While drawing connections between graphs and matroids / vector spaces is beautiful, and FPT, for example, is providing us with wonderful results, I am disappointed by the subfield as a whole.

In general, many of the papers being written have inelegant, and frankly useless proofs, the results of which are wonderful but ultimately feel vapid, revealing no actual insight into the problem, but instead demonstrating a hack around it to get the result, which is a fucking stupid thing to do because the paper becomes useless from a pedagogical perspective. There are a few leading experts that I wish I could get alone in a room and knock some sense into.

There's this misconception about complexity in our field from what I can only see as ingrained insecurity, and honestly, ignorance.

Mathematics is ultimately an abstraction, a symbol game on imagined structures. We should understand this better and construct better, more comprehensible proofs. But then all the hack theorists out there would be btfo, or, my hope in making this argument, would be motivated to actually do things the right way. Which is to consider how your proof actually looks to another person, because right now the majority of them just look sad, and I feel sorry for the pitiful individuals that are incapable of expressing and comprehending simple truths. I would settle for them looking at the right problems, even.

I can hear the peanut gallery now, disagreeing. These are the same folks I am complaining about.

[Anonymous No.11605851]

>>11605846
What did you do in your undergrad? Why did you choose to do a PhD?

[Anonymous No.11605857]

>>11605810
Really cool field, young yet rapidly expanding.
Pic related is from a really good recursion theory text

[Anonymous No.11605864]

>>11605846
Could you provide some examples or some papers with “hacks?”

[Anonymous No.11605870]

>>11605857

Fuck that shit is way too abstract for me. Where would I even begin at finding concrete examples to understand the abstraction? Do you actually try thinking about different types of combinations of turing machines when you're reading this or are you just making inferences based on semantics? Or some combination?

[Anonymous No.11605905]

>>11605870
It’s well past 100 pages into a grad text, so don’t worry about it seeming abstract. I don’t see how “thinking about Turing machines” and “semantics” are two different activities..

[Anonymous No.11605919]

>>11605864

This is most papers, just pick one. If it isn't immediately apparent when you look at most papers on, say, FPT with less than a few hundred citations, then you may be part of the problem. Our field is crowded with people that are willing to sift through the details of complete, over-engineered bullshit and write it off as correct, because it is, mind you, and say that it is not so bad simply to maintain their arrogant facade of being above others. I am honestly afraid of doxxing myself if I tell you the papers I'm thinking of.

But I can think of an instance where instead of letting me in on the insight of a proof, a colleague of mine pointed me to a paper that would have taken a few days to deal with the technicalities of. I then just reworked the proof myself in about a paragraph or two, but it cost me a few hours of my time. And I knew he knew the simplicity of it as well. Honestly, fuck that guy, but I don't think that he is alone in being such a mid-wit solipsist.

>>11605851

I decided I didn't want to work for silicon valley and did research instead.

[Anonymous No.11605920]

>>11605846
>There's this misconception about complexity in our field from what I can only see as ingrained insecurity, and honestly, ignorance.
that being? You’re talking in broad strokes without being specific about complaints.., like you’re shitposting

[Anonymous No.11605963]

>>11605857
>>11605870
>>11605905

Also, ironically, this is exactly what I am talking about. I'm not going to waste my time attempting to diagnose the content of these out-of-context screen-caps, because, anon looking to learn: jump into working on an interesting and impactful problem, and do not bother with those who need to hide behind symbols. You will find yourself with plenty of abstraction when you actually try to do something, but it will be of the natural variety, and not the synthetic, unaware esotericism brought about by drinking the flavoraid.

[Anonymous No.11605967]

>>11605810
Judging by the editorial board, the journal looks quite respectable.

[Anonymous No.11605973]

>>11605920

If you don't see it already, then there's most likely no hope for you.

[Anonymous No.11605994]

>>11605857
Whats the name senpai?

[Anonymous No.11606011]

>>11605919
It sounds like you either had a bad interaction with one (1) colleague or you're exaggerating the claims. I've read papers where people are clearly trying to compensate for their dick size, but the majority of complexity and general theory papers out there are well written. Hell, they're best seen as collections of results since one paper usually doesn't go over much.
>>11605920
>>11605963
oh, I'm beginning to see the picture now. You're either a systems or applications PhD who scoffs at theory that isn't teetering on completely practical. The pages I posted aren't difficult or 'over-engineered' to anybody with a modicum of an undergrad math background - the book I posted is actually quite terse despite being so comprehensive.
> jump into working on an interesting and impactful problem
there are plenty - this doesn't diminish the interesting problems in recursion theory.
>do not bother with those who need to hide behind symbols
you seem to have contempt for any theory that isn't immediately 'practical.' This is theory - the motivation is to do mathematics and develop a theory of computation. yes, every theorist out there also wants to solve problems, but just like with a mathematics department, one wants to balance their time and efforts between exploring new theory and doing new problems.
I get that this isn't your subfield (hell, recursion theory isn't even my subfield of study), but there's little need to say "pssh, I've above it, everyone here is stuffy."

[Anonymous No.11606017]

>>11605994

Not him but this is a computable analysis textbook.

[Anonymous No.11606020]

>>11605973
I mean, I've have nothing but good interactions with my TCS department, save like one older advisor who's a hardass on everyone. I see problems where you're pressured to put out a paper on every single small detail / result you've made, but other than that, I don't see the major 'everything is made too over-elaborate' problem you're talking about. I wouldn't imagine there is a simpler way to exposit an Erickson paper, for example, because it's already written in such a clear manner...

[Anonymous No.11606027]

>>11605994
>>11606017
This is not a computable analysis textbook. It's "Turing Computability" by Soare.
There's some results related to computable measure and analysis towards the end, but most of it leads up to finite injury, jump inversion, forcing, etc.. If you like classical logic, I have a feeling you'll be at home with this book - it's way better than say, Sipser, at actually introducing you to Turing machines as a logic-theoretic framework (ie, it's written as a logic text and doesn't have any pretense of dumbing things down)

[Anonymous No.11606048]

>>11606027

My bad homie. Thanks for sharing your opinion though. Nice to have someone on "the inside" to give us hobbyists the scoop.

[Anonymous No.11606053]

>>11606048
I'm not the guy who was complaining about cs theory academia

[Anonymous No.11606059]

>>11606053

No I know who you are. I'm not the guy who has a problem with theory. I'm just a hobbyist and appreciate you sharing your opinions on the various texts. I am a bit stronger with classical logic than modern math so I'm glad you mentioned that.

[Anonymous No.11606069]

>>11606059
ah, yeah no problem. feel free to ask if there's anything else or any other books you're interested in

[Anonymous No.11606087]

How is learning theory you guys? Good research area?

[Anonymous No.11606094]

>>11606087
It's a cool field. You'll find that computational learning theory and statistical learning theory are both really studied together and in the context of each other. If you like mathematical analysis, complexity, and probability theory, learning theory is a really cool field yeah.

[Anonymous No.11606126]

>>11606094
I'm a code monkey who didn't do enough math or any research in college now I'm romanticizing research careers
Sigh what to do

[Anonymous No.11606129]

>>11606126
Pick up a few books to refresh, get comfortable with some analysis, probability theory, and ask a professor at a local university if they would mind you volunteering for research with them

[Anonymous No.11606147]

>>11606129
Eh I doubt it, they have funded PhD and master's students they're obligated to work with
I thought about maybe doing a second undergrad in the UK in stats or math or something -> PhD

[Anonymous No.11606188]

>>11606147
they have funded phd students yes, so they don't have to pay them. if you volunteer for like half the week or whatever and get some good results, I don't see why they wouldn't let you.
Basically do that, ask the grad director to take some grad level courses as a non matriculating student and maybe getting admission as a masters student for research

[Anonymous No.11606221]

"Theoretical computer science" doesn't exist. Fuck off back to your containment board.
The fucking textbook that the moron was posting pictures from is a RECURSION THEORY text. RECURSION THEORY IS A SUBSET OF MATHEMATICAL LOGIC. IT IS NOT "THEORETICAL COMPUTER SCIENCE."

[Anonymous No.11606226]

>>11606221
why are you on every thread about TCS?
> IT IS NOT "THEORETICAL COMPUTER SCIENCE."
https://www.springer.com/gp/book/9783642319327
>listed as 'Theoretical Computer Science'
nobody agrees with you

[Anonymous No.11606245]

>>11606188
I have to at least be as qualified as their undergrad interns/volunteers. The kids who get in are like 3.9+ GPA kids who can already meaningfully contribute. It's a pipe dream to get some local prof's attention at this point without meaningful results first

Have you ever seen someone publish at a top AI conference without an affiliation (current grad student, FAANG research employee, etc)? I know it's theoretically possible with blind review and all but I haven't seen it. I guess that would be one way to get into a lab somewhere

[Anonymous No.11606262]

>>11606226
>why are you on every thread about TCS?
why do you fucking abbreviate it "TCS"? no one calls it this besides buttmad computer shits who couldn't hack it out in math
i am in these threads because these threads don't belong here, they belong on /g/ your containment board.
FUCK OFF!
>le book listing
oh i guess that makes me wrong huh?
again: there is no such thing as "Theoretical Computer Science," just because you rename a subfield of mathematics and thieve it from hardworking people as if it were ever a part of """Computer""" """""""Science""""""", doesn't make it ACTUALLY computer science.
turing, church, and kleene are ROLLING IN THEIR GRAVES!

[Anonymous No.11606275]

>>11606027
>New Soare
I didn't like it but I learned this stuff from his R.E. sets and degrees.

[Anonymous No.11606320]

>>11606245
I mean yes, there is catching up to do, but this is part of why you should aim to be non matriculating or even matriculating at a grad level. What catches a prof's attention is labor that doesn't involve monetary trade, since that shows a combination of drive and initiative. Yes, obviously your professor can't focus on you as much as members in the lab, unless you make yourself useful. Don't expect top labs. The whole point is to *build yourself up* in baby steps.
Your post sounds like you're self-loathing and want more reasons not to pursue this or to defer your study. I get it, but if you're here to list the reasons as to why it may not work, then you're just kicking yourself. You might as well chase it.

[Anonymous No.11606327]

>>11606262
>no one calls it this besides buttmad computer shits
it's a common name for the field from both within and outside the department...
>who couldn't hack it out in math
most of the top TCS professors have math or CS PhD's with dual appointment to both departments. Yes, there are CS PhD's in math departments.
what is 'computer science' to you if not a part of math?

[Anonymous No.11606332]

>>11606275
I like the book a fair bit actually. He's really enthusiastic about the subject and it shows in the writing.
His exercises, even though they're not as plentiful as I'd like them to be, are really good

[Anonymous No.11606365]

>>11606327
computer science is a fake name given to a bunch of people who waste university funding to masturbate all over industry
computers are not a science

[Anonymous No.11606395]

>>11606365
>masturbate all over industry
computer science and industry are two different things lmao. name me a topic in TCS. no mentions of AI, ML, or systems CS.
>computers are not a science
studying computation is mathematics.

[Anonymous No.11606414]

>>11606395
I can't name you a topic in TCS, I can only name you a topic that YOU would call a topic in TCS even though it isn't.
>Recursion theory, hierarchy of computability
>Convex optimization theory
>Complexity theory and the intractability hierarchy

[Anonymous No.11606422]

>>11606414
I mean these topics have been studied extensively in TCS departments. Same goes for domain theory, computational topology, etc.. I know you're shitposting, but there are people here who think any part of CS that is pure 'belongs' to another department

[Anonymous No.11606428]

>>11606320
Yeah I know. I've thought about moving closer to applied ML or even research ML on the tech industry side but I've heard it doesn't really bring you any closer to being a PI / full time researcher if you work on applications or work on another person's ideas instead of generating your own

Are you a grad student?

[Anonymous No.11606433]

>>11606428
it doesn't bring you closer unless you work on research, yes. However, what it does do is give you an in for graduate studies, where you can start building up to being a full researcher.
>are you a grad student
yes but not in ML

[Anonymous No.11606442]

>>11605810
dude it's so boring don't waste your time

[Anonymous No.11606452]

>>11606442
lol what's boring about it

[Anonymous No.11606496]

>>11606433
Nice what field? Do you feel like 1:1 meetings with your advisor enlighten you in ways that you can't find elsewhere? That's like the whole point of grad school right, besides the degree/working full time on getting publications

[Anonymous No.11606739]

Is TCS to math what ML is to statistics?

[Anonymous No.11606871]

>>11606496
>Nice what field
communication complexity and computational topology are my two big interests right now
>Do you feel like 1:1 meetings with your advisor enlighten you in ways that you can't find elsewhere?
yes, definitely. you get a lot of direction from your advisor, as well as an in to talk to other people. Picking a good advisor is one of the most important things you can do - and a lot of that comes down to seeing where their grad students went afterwards. It's not necessarily about their fame or w/e, but whether they're a good guide for the future.
>That's like the whole point of grad school right
it's about being exposed to the environment at large, which is both your advisor, other PI's, other students, etc.. Building a network and learning how to collaborate and research is one of the biggest lessons grad school can teach you. We like to think we're lone wolfs, but we're just small imps climbing on the shoulder of great work behind us, and it's a much better process when we're hoisting each other up rather than trying to tear each other down. It's not as idealistic, but I get the general impression people in this field are interested in advancing their career by cooperating rather than spending the effort to try and out-edge them.

[Anonymous No.11606883]

>>11606739
Not exactly, since TCS isn't just application of mathematics. There is a lot of mathematical research on the bed of TCS with the foundations (recursion theory, basic complexity) has been done since the 60s, and now TCS is a fully fledged *field* which a mix of motivations inherited from both math and engineering - that is, there is some TCS that is just like pure mathematics (domain theory) and some that is liked applied mathematics (subsets of algorithms research), and some in-between. ML vs statistics isn't nearly as large in scope, especially since theory of ML (computational / statistical learning theory) is a TCS topic lol

[Anonymous No.11607184]

>>11606871
Dope man, I'd love to do that. Did you major in math? It would've been too hard for me back in school days to keep up in classes, try to do research, code projects on the side, and prepare for job interviews. Idk how people do that shit. I was the guy who fucked up several grades because I was optimizing for internship/job hunting. Maybe if you have more generous curves in undergrad that'll help free up time, at my school you can really drop into the C and below range fairly easily if you're not keeping up

[Anonymous No.11607200]

>>11606365
>>11606395
peanut brain detected

[Anonymous No.11607224]

>>11607184
>Did you major in math?
I double majored in math and CS
> It would've been too hard for me back
yeah I get the feeling, but I think people seriously underestimate themselves. That being said, it's not all about academics
>I was the guy who fucked up several grades because I was optimizing for internship/job hunting.
that makes sense, though I've found that these days especially you don't get an internship without at least decent (ie, 3.0) grades unless you have connections.
>Maybe if you have more generous curves in undergrad that'll help free up time
I've found that both the math and CS programs here are fairly hard and don't curve *super* easily, but also if the average is something like 35 for a topics in complexity class, obviously something like a 60 is going to be an A. I'd say that if you've gone through undergrad once, you have more than enough background to start learning on your own and maybe getting some experience in research / labs out there. Good luck anon, I believe in you

[Anonymous No.11607227]

>>11607200
two different posts by two different people with two opposing points here anon, exactly which one are you talking about?

[Anonymous No.11607256]

>>11607224
>>11606871
>computational topology

That seems like such a cool field to study. Is it gaining in popularity or is it still somewhat under the radar? I remember when I heard about it a few years ago it seemed very novel. What is it like doing research? Do you feel like your peers are more or less at the same level of understanding on any given topic/concept?

I'm kind of a fuck up and am stuck working low paying jobs and trading stocks with the little amount of money I have to earn anything so I never really get to talk to people about "pure" math except on /sci/. I imagine it must be a dream to be a graduate student in math.

[Anonymous No.11607332]

>>11607224
Thx anon

[Anonymous No.11607401]

>>11607256
Try computational geometry sometime
https://people.inf.elte.hu/fekete/algoritmusok_msc/terinfo_geom/konyvek/Computational%20Geometry%20-%20Algorithms%20and%20Applications,%203rd%20Ed.pdf

this is from CMU's real world algorithms
https://www.cs.cmu.edu/afs/cs/project/pscico-guyb/realworld/www/slidesS18.html

>>11607332
one of the leading complexity researches has open courses on youtube https://www.youtube.com/channel/UCWnu2XymDtORV--qG2uG5eQ/playlists

All those courses are amazing, esp his 'complexity theorist tool kit' which teaches adv math, and his Quantum computing course which teaches the information theory model of quantum computing.

[Anonymous No.11607557]

>>11606422
i'm not shitposting, i actually think that and i'm right

[Anonymous No.11607590]

>>11607256
>Is it gaining in popularity or is it still somewhat under the radar?
it's gaining popularity but it's not as mainstream as combinatorial algorithms, for example. It's a very interesting field, and it allows me to study various subfields of topology while also studying computation - and while there's still a lot of work to be done to having the TCS topology catch up with the high powered topology results in mathematics at large, it's really nice to see how far we can take algebraic topology results.
> What is it like doing research?
exhilarating but very energy intensive. I can see how it's easy to get caught in a rut of being lazy post tenure
>Do you feel like your peers are more or less at the same level of understanding on any given topic/concept?
in my subfield for sure. not throwing any shade, but I do feel like various CS researchers (especially those outside of theory) aren't nearly as strong in mathematics as they ought to be..but I'm not going to sit and judge, especially since many of them have since covered their bases.
> I imagine it must be a dream to be a graduate student in math.
I'm in the CS department, but my time is basically split between reading books in pure math and TCS and doing theorems, so I suppose I could consider myself a "student in math" less concerned with existence results in topology and more with existence of structure, algorithms, technique, on top of the old results that admit interesting work in computation, theoretical or practical. I think my heart still lies in math and I might end up veering towards pure topology results later in my career, but for now I think there's a serious amount of work needed to build up computational theory to say the H book, so I'll work where the work is wanted.

[Anonymous No.11607591]

>>11607401
The Theorist's Toolkit is a wonderful resource to broadly useful mathematics across TCS, and you can use various other books in mathematics to append to your specific needs (ie, read more analysis books and measure theory books if you work in randomized algorithms / complexity or resource bounded measure, read more topology for computational topology or robotics, etc etc.)

[Anonymous No.11607595]

>>11607557
ok but you're clearly wrong

[Anonymous No.11607668]

>>11605846
anon, what courses did you find most valuable for TCS as an undergraduate? at my school, we get to pick our own upper electives in both mathematics and CS.

[Anonymous No.11607958]

>>11607668
not him, but it depends on what you want to do. Generally now most mathematics is useful in TCS in some way, but the most mainstream topics will benefit from the following:
Combinatorics
Graph Theory
Number theory
Probability theory
Stochastic processes
Recursion theory and classic logic
Abstract Algebra (ring theory, representation theory, algebraic number theory are most used)
Linear Algebra (obviously proof based)

Less 'mainstream' but also very useful / interesting / well studied subfields:
Analysis (complex, sometimes real as well) (theory of probabilistic algorithms)
Analytic combinatorics (complicated structures, average case analysis)
Algebraic topology (comp topology, distributed networks, graphics and noise)
Analytic number theory (cryptography, codes, but there needs to be more connective work here)
Algebraic geometry (communication complexity, recently biggest lead on separation bounds between P vs NP)
Differential geometry (Vision and learning theory, animation and graphics, computational geometry)

What are your interests anon?

[Anonymous No.11608090]

>>11607595
every time you abbreviate it "TCS" another little part of me dies
can't you just call it computer science
what is the difference between computer science and Theoretical Computer Science?
>>11607958
this is just like 70% of the fields of math you fucking moron

[Anonymous No.11608118]

>>11608090
can't you just call it physics
what is the difference between physics and applied physics?

[Anonymous No.11608126]

Nigga finna get dabbed on lmao

[Anonymous No.11608149]

>>11608090
>what is the difference between computer science and Theoretical Computer Science?
the latter is a subset of the former. You wouldn't put ML, systems, compiler engineering, network design, etc., into the theoretical computer science camp. On the other hand, complexity theory, domain theory, computational geometry, etc., are firmly in the theory camp for fairly obvious reasons.
>this is just like 70% of the fields of math you fucking moron
...yes and? These are all relevant topics in CS. Anon clearly asked for recommendations for electives. For TCS, these are valuable - I'm sure anon already knows to take complexity theory and computability in undergrad. These are all the relevant topics to get into basic TCS topics.

[Anonymous No.11610002]

>>11606739
No

[Anonymous No.11611721]

What are the pre-requisites for TCS?

[Anonymous No.11611774]

>>11608149
you're confirming that you're the solitary tee cee ess shill in this thread.
>>11611721
sub 80 iq

[Anonymous No.11612103]

>>11605967
it's not.

[Anonymous No.11613393]

>>11611774
>shill
not really? Study what you want, but how is "TCS is not what you think it is" shilling? Is it the idea that TCS is as professional and difficult as math and mathematical sciences like math and physics something that bothers your choice of another subject? Do you have to convince yourself that TCS is completely without merit in order to be comfortable studying something else? If not, then how could anyone see this as "shilling?"
>>11612103
evidence / proof?

[Anonymous No.11613627]

>>11605810

let me be honest

1. n+10^{gazilion number of parallel universes}=O(n)

yet for most n is just fucking big

2. Turing machine WITH AN INFINITE memory is a model of computer - are you kidding me?

3. look I have used category theory - now what?

4. incredible mess in (some) books, have you ever heard - definition, theorem proof, not just your feelings

5. SVD is a "unsupervised machine learning"

and so on and so on

but still cool and based

[Anonymous No.11613959]

>>11613627
>n+10^{gazilion number of parallel universes}=O(n)
...no, that's O(10^n)
>Turing machine WITH AN INFINITE memory is a model of computer - are you kidding me?
important for talking about computability and recursion, but don't be obtuse - in complexity, the problems all halt in finite time, and each step of the computer can write 1 thing to the tape - obviously these algorithms are finite space, especially since space complexity is a big topic
>look I have used category theory - now what?
where did this come from?
The rest of your points are schizo

[Anonymous No.11613968]

>>11613393
every one of your questions is predicated on false premises, attempting to turn this around as some kind of insecurity on my part
you're projecting

[Anonymous No.11613996]

>>11605810
Theoretical Computer Science is a math journal. How could /sci/ have an opinion on a math journal? Is it like if they even know how to read?

[Anonymous No.11614078]

>>11613968
>every one of your questions is predicated on false premises
elucidate, since there's nothing obviously false about anything there.
>attempting to turn this around as some kind of insecurity on my part
nah I think you're shitposting but I'm more than certain at least a few people on this board feel this way.

[Anonymous No.11614837]

>>11613627
>>11613959
1.) no, that's O(n) as n tends toward infinity, which is larger than 10^{gazillion brain cells I lost reading this}. Any number pales in comparison to literal infinity.

2.) *model of COMPUTATION, defining what is computable

3.) I guess we can't cross fields anymore, better stop using English to write papers

4.) Bad books aren't written anywhere else?

5.) You understand SVD is used in reduction of dimensions to make the computation more efficient for machine learning right?

Dammit, you made me reply. 10/10 trollan.

[Anonymous No.11615460]

>>11613996
I have a paper in it and this is a low quality journal.

[Anonymous No.11616472]

>>11615460

Hi, hobbyist here. What is the difference between a high quality and low quality journal? Errata? Style of writing? Difficulty of problems solved per paper? Status of people contributing to it? Average number of citations per paper? Editorial oversight?

[Anonymous No.11616487]

>>11616472
No. of citation per publication, their impact factor, and also the no. of high-quality images.

[Anonymous No.11616490]

>>11605810
very based

[Anonymous No.11616510]

>>11616487

Does the quality of the journal matter? Does the fact that you have more papers published mean more than having less papers published or is it like the "sum of the impact factor of your papers" that matters.