What is there to theoretical computer science...

Images are sometimes not shown due to bandwidth/network limitations. Refreshing the page usually helps.

You are currently reading a thread in /sci/ - Science & Math

You are currently reading a thread in /sci/ - Science & Math

Thread images: 5

What is there to theoretical computer science besides the P vs NP question (a random, completed isolated from the rest of math puzzle)? Is theoretical computer science even a legitimate field of math?

>>

>>7777505

>Is theoretical computer science even a legitimate field of math?

No

>>

>>7777506

lmao

>>

>>7777505

who is this cum chum

>>

>>7777506

oouuuuh I've been looking fo rthis pic for quite a while ty anon

Also, OP

>

>>

>>7777505

Don't come at me with that bullshit OP:

Graph Theory. Combinatorics. Number Theory. Stats. Optimization. Control Theory, Machine Learning for starters. Coinductive Logic

Recently the graph Isomorphism problem was proven to have quasi-polynomial complexity.

Attended a live talk given by Babai.

Im working on expander graphs and psuedo randomness.

CS is a set up to start with the application end and work your way to the bottom levels

AND not be some washed up high school math teacher after we graduate.

Thats about it.

Also P = NP is the biggest psudeo-meme in our field. No CS academic gives a shit about it and generally ends up focusing on more worthwhile problems.

>>

>>7777595

>Recently the graph Isomorphism problem was proven to have quasi-polynomial complexity.

And...

>>

>>

>>7777595

Studying in Chicago?

Could you redpill me on Ketan Mulmuley and his GCT program?

How can you be an animufag whilst not being a complete failure?

>>

>>7777505

What country was that photo taken in? and where can I get baconzitos?

>>

>>7777687

Assland aka Brazil.

>>

>>7777595

>Also P = NP is the biggest psudeo-meme in our field. No CS academic gives a shit about it and generally ends up focusing on more worthwhile problems

This is kind of bullshit.

You will not find a computer scientist who wouldn't kill for a proof one way or the other but the problem is so inaccessible to proof right now that not many people want to waste their time.

That doesn't make it a "meme" (when did we start calling things memes to invalidate them anyway)

>>

>>7777505

Off the to of my head there is.

Computability

Category theory

(Dependent) Type theory

Homotopy type theory

Programming language theory

Theorem provers

>>

>>7777836

Did you take it?

>>

Theoretical computer science is fine, anon.

But most colleges are weak on that side.

If you go to a good one, relax and enjoy, it's a legitimate field.

Here's an example for you.

https://www.quantamagazine.org/20151124-kadison-singer-math-problem/

>>

>>

>>7777506

Funny, because Graph Theory and Combinatorics are Discrete Mathematics, which is part of Computer Science.

>>

>>7778729

No, but there's more here.

http://www.jujusex.com.br/2014/03/que-bumbum-e-esse.html?zx=55e41bc37e11a07

>>

>>7778745

>graph theory and combinatorics are part of computer science

Get a load of this guy.

>>

>>7778745

>He thinks you learn Graph Theory and Combinatorics in Discrete Mathematics

laughingwhores.jpeg

>>

>>7777505

I'm sorry f.m, I'm sure you have a very interesting subject for you thread but I am only here for that bomb af booty

>>

>>7777505

need sauce, for scientific purposes

>>

>>7778756

At least in the book I used they taught you the basics of graph theyory and combinatorics

>>

>>7780042

>>A graph is a set G={V,E} where E⊆VxV

>I now know graph theory you guys! Aren't I kool!

>>

>>7780042

Every discrete math class gives you a tiny taste of those fields. However those fields are gigantic and only an idiot would claim they "know it" after taking a discrete course. I'm not saying that graph theory and combinnatorics aren't covered in computer science to a significant extent, just that discrete math is literally babby's first math class.

>>

>>7780022

The beach

>>

>>7777505

>Is theoretical computer science even a legitimate field of math?

Yes. There are a lot of problems in complexity theory alone. And then you also have automated theorem provers, very interesting stuff.

>>7777506

CS is by very definition a subfield of maths. You are confusing this question with the quality of a CS degree itself.

>>

>>7780165

Still banished to the kiddie table until further notice

>>

>>7780165

>>CS is by very definition a subfield of maths.

look at this undergrad. at best, large branches of math are subfields of CS.

>>

>>7777506

>mathematical logic

>disconnected from computability theory

u wot

>>

>>7778756

>He thinks discrete mathematics refers only to one specific lower level course.

Discrete mathematics is literally just the name for all mathematics that's, well, discrete. This includes combinatorics and graph theory. It also includes number theory and various other areas.

In fact, there is a discrete mathematics seminar at my school focusing on graph theory problems. And the graduate level discrete math course here is the hardest mathematics course on campus.

>>

>>7780125

And if you're not just taking an intro class to CS, you should be doing a lot more. I'm a CS major and I've done 5 discrete math courses in the math dept and I've had 4 graph-heavy (as in course is 60%+ graph theory) courses in the CS dept.

Although that said, "discrete mat" is really fucking vague.

>>

>>7780272

My university only has a graph theory + combinatorics class for undergrad pure math and some crazy hard grad level courses in combinatorics (in pure math as well).

Our CS department is more math heavy in different ways though. We have lots of formal language and computability courses (basic, CFG/compiler stuff, recursive function theory/other stuff), courses on functional programming (type theory, lambda calculus, etc..), a proof theory course, a computational algebra course, a category theory course, a homotopy type theory course, and then the general complexity courses, operating systems courses, and computer architecture courses.

As far as I know we don't have any graph grammars or computable geometry courses. There are a few crypto courses taught in both pure math and comp sci (same classroom and lecture, just listed twice) and some computational number theory courses in the pure math department.

>>

>>7780268

>graduate level discrete math course

These don't exist. There are graduate combinatorics classes, graduate graph theory classes, graduate analytic/algebraic number theory classes, but no shallow survey class.

>>

>>7780255

It's true. You might be thinking of recursion theory, which has nothing to do with computability theory. Computability theorists care about reducibility more stringent than Turing reducibility, e.g. polynomial reducibility. No logician cares about what computability theorists care about.

>>

>>7781067

>Computability theorists care about reducibility more stringent than Turing reducibility, e.g. polynomial reducibility.

You've for your fields messed up. That's complexity theory, not computability theory.

Though as an aside, logicians do care about complexity as well. Without it, for example, all proof system for propositional logic are equivalent, as you can simply ignore any proofs and use your exponential-time SAT solver to check propositions for theoremhood in propositional logic. The thing that sets apart reasonable proof systems for propositional logic, like natural deduction or modus-ponens-only, from "broken" ones is the ability to check a proof on polynomial time. The same problem plays a role in all other proof systems as well, though in those cases the examples are less clear.

>>

>>7781083

Oh, yeah, I meant to say theoretical computer scientists, not computability theorists. Computability theory is sometimes used as a different name for recursion theory. Thanks.

>>

>>7781067

Like the other anon pointed out. Computability is recursive function theory. You're thinking complexity.

I'd argue there's a close relationship to mathematical logic in the more theoretic side of CS.

>>

Computer Graphics is mostly applied neurology these days, it's about using the knowledge of how human visual system works to create imaging systems that would be indistinguishable from reality.

>>

>>7781009

You are entirely wrong, seeing as it does exist at my school.

It doesn't serve as an introduction to combinatorics or graph theory, those are separate undergraduate classes (I've taken or am taking both). Here is the course description:

Methods of discrete mathematics with applications. Generating functions and Lagrange inversion, partition theory, permutation statistics and q-analogues, posets and Mobius inversion. Additional topics including lattice paths and basic hypergeometric series.

>>

>>7782455

Sorry to break it to you m8, but your school is stupid.

Thread images: 5

Thread DB ID: 418358

All trademarks and copyrights on this page are owned by their respective parties. Images uploaded are the responsibility of the Poster. Comments are owned by the Poster.

This is a 4chan archive - all of the shown content originated from that site. This means that 4Archive shows their content, archived. If you need information for a Poster - contact them.

If a post contains personal/copyrighted/illegal content, then use the post's