When did computer science theory get so hard?
blog.computationalcomplexity.org
blog.computationalcomplexity.org
> 1) When you get older math got harder.
> 2) When math got more abstract it got harder. Blame Grothendieck.
> 3) When math stopped being tied to the real work it got harder. Blame Hardy.
> 4) Math has always been hard. We NOW understand some of the older math better so it seems easy to us, but it wasn't at the time.
> 5) With the web and more people working in math, new results come out faster so its harder to keep up.
> 6) All fields of math have a period of time when they are easy, at the beginning, and then as the low-hanging fruit gets picked it gets harder and harder. So if a NEW branch was started it might initially be easy. Counterthought- even a new branch might be hard now since it can draw on so much prior math. Also, the low hanging fruit may be picked rather quickly.
Personally I think it is mostly 2 and 3. And a lot of it has to do with how math is communicated. The very abstract way that math textbooks use to communicate is not how most mathematicians think when solving problems. A lot of things I struggled to learn from books became much more understandable once someone gave me the little insight I needed to make sense of it in conversation.
Why? How are they different?
I had three reactions:
1) I was elated to finally understand sin and cosin.
2) I was thankful for him and also amazed at how simple it was in 5 minutes to explain something that seemed to have eluded me for 5 years of highschool. It made me wonder alot what other difficult subjects could be easily taught by just a good explanation.
3) I wondered why math class had failed so specifically to give me that knowledge, or at least test me to see if I understood it and if I didn't to ensure that I did understand it. The answer I think was math class just encouraged me to use a calculator, thus short circuiting any real understanding.
Anyways he went on to be a physics professor at Cambridge.
I always appreciated that moment.
It's possible back in the old days the math teacher did mention it, but we couldn't understand it at the time because we had little sense of the subject.
A common take on this phenomenon is discussed here occasionally:
http://habitatchronicles.com/2004/04/you-cant-tell-people-an...
For a demonstration, go back and watch a good movie that requires focus, say three times in a row. Every viewing should uncover details you didn't notice the first time, because we can't take them all in at once.
It's also why repetition is a good learning technique. Unfortunately few people have the patience to start over from the absolute beginning.
At your current age, you are more capable in some ways, less in others, and thus your learning capacity is different.
It's subtle, but I think it's a very valid point since I too never thought it in terms of ratio, merely in terms of here's the angle, this is what you need to find, you apply sin/cos/tan and get the answer.
If you somehow managed to skip trigonometry in high school but still got into college calculus, then there are a few of other ways they might be defined.
One way is to put off dealing with trig functions until you get to differential equations. Then sin is the unique solution of y'' + y = 0, y(0) = 0, y'(0) = 1, and cos is the unique solution of y'' + y = 0, y(0) = 1, y'(0) = 0.
Another way is to define them axiomatically. These are the axioms for sin and cos:
1. They are both defined everywhere on the real line,
2. cos(0) = sin(pi/2) = 1, cos(pi) = -1,
3. cos(y-x) = cos(y) cos(x) + sin(y) sin(x)
4. for 0 < x < pi/2, 0 < cos(x) < sin(x)/x < 1/cos(x).
From that you can deduce all the usual trig identities and the limits you need to do calculus with them.
You still need to prove that functions satisfying those 4 axioms actually exist. One approach is to put that off until later when you've got more tools under you belt. For example once you do Taylor series, you can work out what they Taylor series would be for sin and cos if they exist. The functions defined by those Taylor series do exist, so then you just need to show that those functions satisfy the axioms.
But all of these require calculus and quite a lot of hand waving about real numbers and limits and infinite sums, especially in a high school context. And most of their applications (per se) are pretty advanced.
At the high school level it’s probably best to explain that angle measure per se is a very tricky concept (an angle measure is a type of logarithm). We can get a very long way without ever having any explicit "angle measure" concept. E.g. there are no angle measures anywhere in Euclid’s Elements. (Angle measures come from astronomy and navigation.)
We can look at the complex coordinates of 2D rotations (points on the complex unit circle) without ever trying to turn that into a single scalar-valued quantity. And should do that in a lot of circumstances where angle measures are currently used. In e.g. geometric simulations (computer graphics, robotics, computational geometry, ...) it’s best to avoid angle measures as much as possible, and stick to vector algebra.
An angle measure "is" a logarithm of a planar rotation with the orientation stripped away. That is, the structure of angle measures is isomorphic to these logarithms. (Planar rotations are most naturally represented by a quantity like a + Ib, where I is a unit bivector and a and b are scalars with a² + b² = 1.)
Logarithms need comparable amounts of technical machinery to define as arclengths, so there’s no difficulty advantage in considering an angle measure to be an arc length or the area of a sector instead of a kind of logarithm. Conceiving of a logarithm of a rotation as being the same quantity as the area of the associated circular sector can be a helpful mental picture though (and there is no need to even strip out the bivector’s orientation if you use an area).
You can calculate the length of an arc associated to a triangle by simple comparison to a known angle such as the quarter angle and its products, this will allow you to finitely compute any rational angle. This is the conceptual basis for using arclengths.
To formalize this, you can define trigonometric functions now, and you can use them to introduce polar coordinates, and by translation of the intersection to the origin, show that you can calculate the angle for all real numbers by construction of a right angle triangle and now determine the sine as the ratio of two real numbers, etc...
It is wholly unnecessary to introduce logarithms. Yes they are isomorphic. They are also unnecessary. So are bivectors. Angles are perfectly well defined without anything but basic algebra and some geometry. You really just need an extensible definition of the trigonometric functions to provide rotation and you've got yourself a perfectly sound definition.
And note that an "angle" and an "angle measure" are two separate concepts.
> finitely compute any rational angle
Sure, we can calculate specific logarithms without a formal definition as a function over a continuous domain, based on some stated rules for formal manipulation, taken as axioms. Not just rotations, but also scalar logarithms. For example, we can precisely calculate the logarithm base 2 for any arbitrary rational power of 2: log₂ 2^(p/q) = p/q.
A "rational angle" is nothing but a rational power of –1: Arg (-1)^(p/q) ≡ (p/q)π (mod 2π)
The rational angles are only used to introduce the trigonometric functions. From then on we can deal with any real angle using arcs of circles and trigonometric functions.
Therefore we don't have any issues. We can deal with angles perfectly well as long as we can know the circumference of a circle.
Whereas otherwise we would need either calculus or complex numbers, but we need geometry to make sense of them and we need angles to make sense of geometry without handwaving or making it needlessly difficult to learn.
In other words, an angle measure isn't a logarithm, a logarithm is equivalent to an angle measure when we accept constructs that are not necessary but are sufficient to angle measures.
This whole technology is built on a foundation of calculus (limits, infinite sums).
> we need angles to make sense of geometry
Euclid’s version of geometry involves no angle measures whatsoever. Vector methods (of the type which should be preferred for most geometrical modeling and computation) generally need no angle measures.
Angle measures get useful when dealing with uniform circular motion: astronomy and navigation, signal processing, etc., but are largely superfluous for geometry per se.
I didn't understand what functions are/ how they work, my brain absolutely refused to understand, until i started programming. Then i got it in 5 minutes.
I don't know if it has to do with how my brain works. I wouldn't say i have too technical mind.
such a shame. sounds like a talented fellow who really could have made something of his life. maybe even a chair at Oxford :/
The responsibility for not knowing until that point is more likely to be on my shoulders than the lecturer's, however.
Explain?
Overall what I've found is that older textbooks (edit: not just math) are more likely to (1) explain concepts in smaller steps; (2) not bury them in symbols and abstractions; (3) introduce and explain physical intuitions for subjects when they are relevant.
to learn anything, so you can teach it to somebody else (the REAL def of Learning I'd say), you have to Do The Exercises.
---- I recently went over one of my older books on Matrices and it was a curious mix of trying to be sort-of precise, with trying to bring the 'wonder' and 'magic' of the concepts to life early -- so as to maintain reader interest. Ultimately, it was the way of thinking (mathematically) that was mostly taught; the 'matrix intro' was just fodder to support the pedagogy!
Try reading the example on that page. That is what makes math hard. Not the way calculus is described.
When it gets into the symbolics of the ethereum state machine (section 4+), things get hairy fast. Unfortunately papers like this only make sense once you understand the paper. It's a succinct representation of knowledge for someone skilled in the field, but not a sensible way to teach others about the EVM.
Sounds like manpages (:
> took some upper level analysis courses
Real Analysis is still not very abstract, but yeah that is a step. The next step is to remove everything concrete about it and just study abstractions. And then you start studying abstractions of those abstractions, hence "abstract nonsense". Maybe sometimes in the future someone will invent abstractions of those.
Edit: Meant the stuff you learn in Rudins principles of mathematical analysis. Not sure exactly what the course would be called in an English class, but I called it real analysis here.
I'm not saying you would, I'm just saying the abstractions are directly related to why its harder.
> since you still want those explanations, but they stop existing after a point.
You're misunderstanding me.
> The next step is to remove everything concrete about it and just study abstractions. And then you start studying abstractions of those abstractions, hence "abstract nonsense". Maybe sometimes in the future someone will invent abstractions of those.
Yes, I understand all this. I have the textbooks and I've read parts of them. The reason I didn't study math more seriously (I considered it) is because I realized I didn't have the brain for it and am not that interested in studying really abstract stuff.
> In mathematics, abstract nonsense, general abstract nonsense, generalized abstract nonsense, and general nonsense are terms used by mathematicians to describe abstract methods related to *category theory* and homological algebra.
Oh so _that_ is why I can't understand Haskellers..
Don't just leave us hanging :-) Care to elaborate on what helped gain that insight?
I sometimes wonder if we'd be better off telling teenagers that the motivation they need to learn math is self-preservation. There are always people who are going to try to trick you with bad math (from misleading cost/benefit analysis, to financial malfeasance, to bad faith public policy debates) and if you know some math they can't do that to you.
The "you give Timmy five apples" shtick is almost anathema to that. You've practically built a narrative for the kid to get distracted from the point of the exercise. I don't like Timmy, or I don't know who the hell Timmy is. I'm not giving him five of my apples. Timmy can go fuck himself. Get your own damn apples.
Better: you put twenty skittles into a cup. You drop the cup, and there are only 5 skittles left in the cup. How many are on the floor/how many do you need to replace the lost ones?
I use arithmetic logic and geometry and occasionally some basic statistics.
The answer was always "theres a lot of applications if you get a math job" to which we all groaned imagining counting cups of skittles and mentally dividing while the computers sat idle...
I need to start collecting examples of conclusions drawn from incomplete and / or poorly explained statistics. I did three levels of statistics, and found it boring because I struggled to find how it would be useful in my future career. I'm eternally annoyed at myself for not paying enough attention, I love stats now.
One interesting (and divisive) example for statistics was way early in the COVID timeline the talk about reaching herd immunity through "just letting it propagate" as per the narrative around Sweden's approach.
The required herd immunity figure was something like 60%[0] at the lowest end. In the US daily new infections peaked in January 2021 at 305,000[1], and the US population is around 330 million[2] (with 60% being 198 million).
At that maximum rate of new daily infections, it would take 649 days (1.77 years) to reach herd immunity.
The average daily new infection rate from the 21st of March 2020 to the 15th of November 2021 is ~79,500. At that rate it would take 2,490 days (6.8 years) to reach herd immunity.
In both of the above scenarios, with a fatality rate of 1%, there would be 1.98 million deaths during the time span.
Other numbers that would be interesting in context:
- Number of hospital beds
- Number of ventilators, how quickly they can be manufactured, how long they're dedicated to an individual case (and bonus points for recovery rates of those who needed to use a ventilator)
- Medical oxygen usage rate and availability (India had an issue with running out of medical grade oxygen[3], although it may not be as much of an issue for more countries with more advanced infrastructure)
Thank fuck for medical technology and vaccine development (the age we live in!)
[0]: https://www.sciencemediacentre.org/expert-comments-about-her...
[1]: https://www.worldometers.info/coronavirus/country/us/#graph-...
[2]: https://en.wikipedia.org/wiki/Demographics_of_the_United_Sta...
[3]: https://www.theguardian.com/world/2021/apr/29/explainer-why-...
CS theory always had hard math. Software engineering didn't (and still mostly doesn't) but also in the 1970's software didn't exist so you could literally do anything and it would become the standard if it was pushed hard enough.
It's not like there's an intrinsic reason TCP packets are the way they are now, it's largely an arbitrary choice that we standardized on.
IP and TCP were very carefully designed and were not much like the networking standards of the time. It wasn't an arbitrary choice any more than designing a rocket engine is an "arbitrary choice".
The point was basically that history is ‘arbitrary’, at a larger scale than the intention of the TCP design or the reasons it got chosen for standardization. Maybe the primary reason that TCP stuck is because the military committed to it first, and that signaled to the rest of the world that it was good enough.
It doesn’t necessarily require competition for something to be arbitrarily canonized or standardized, things just happen the way they happen. There can be good reasons all along the way, but it still could have happened a different way, and just didn’t. TCP does choose some specific tradeoffs, it’s not the only way the internet could have come about. Being first without competition is one way it happens. When this happens it adds enormous friction to later alternatives that have or make different tradeoffs.
Yeah, I get that, and of course everything is a spectrum, including the level of arbitrariness. But I am just going by the definition of arbitrary in a dictionary:
> arbitrary, adj. based on random choice or personal whim, rather than any reason or system.
Whereas my analogy with rocket engines was meant to illustrate that IP was designed to solve a very specific problem given a set of constraints. Most (let's say, liquid-fueled) rocket engines end up with very similar designs and engineering decisions are made to optimize performance rather than whim. It's a very empirically-driven engineering exercise.
And for the OP's mentioning of the TCP packet format, I still think we shouldn't regard that as arbitrary. The location of the source and destination fields, for example, was carefully chosen so that routers of the time could minimize the logic necessary to decode them and start to make routing decisions before even most of the header had arrived. It was literally optimized down to the bit position. Now, the choice of byte order (big endian), we might be considered somewhat arbitrary (maybe even wrong) now, but even that was motivated by the machines of the time, as most were big endian while nowadays almost all remaining architectures are little endian (causing no end of confusion to poor networking students).
I don't disagree that history overall, and computer history in particular is full of arbitrary choice points, but I think TCP/IP isn't a good example of that.
> It's not like there's an intrinsic reason TCP packets are the way they are now
This to me invokes the idea of mathematical intrinsic properties. For example the idea of the number zero didn’t always exist, but to this day we don’t have multiple representations or any alternatives. Something about the number zero feels intrinsic. Addition, multiplication, derivatives and integrals seem like operations that might have different notations, but are unchanging intrinsic concepts. TCP formats don’t seem to share this intrinsicness. It is in that sense that I agree with the top comment; there is nothing intrinsic about the TCP format, it is the result of conscious engineering choices, and today there are reasonable alternatives. In this sense I see your argument as supporting this idea that there’s nothing intrinsic about TCP.
> it's largely an arbitrary choice that we standardized on.
The word “arbitrary” was applied to the choice of standard, not the format. I’m choosing to see a second, different idea in that second clause. I see how and why it implies the format itself is being called arbitrary to you and others, but my defense of the comment is based on interpreting it differently than what you saw.
BTW, the dictionary definition starts with “based on random choice”. If we stop there, it still adequately matches what I was talking about, and it also unfortunately doesn’t add much color either. Then the keyword becomes “random” rather than “arbitrary”, but “random” is also commonly used to mean the reason is unknown or complex.
Total tangent, but being a fan of Monte Carlo methods, I frequently use “arbitrary” to disambiguate from truly “random”. When people are asked to pick random numbers, the results are arbitrary but not random in the mathematical sense. ;)
Yes they were, very literally, and incorrectly to boot
Being first is not arbitrary. It is hard to achieve, and valuable. It is a reason.
There were networking systems before TCP and alongside TCP, TCP was clearly superior for a large number of reasons.
Given that everyone on hacker news's livelihood stems from the awesome of TCP (not an over statement), I propose a bit more respect.
How did it happen that the byte order of the multi-byte numeric fields in TCP/IP headers is big endian, which is opposite of what most machines use now? Back then, did it look as if big endian would become prevalent?
Today, almost every host attached to an IP network has to byte swap.
The IPv6 people definitely ought to have designed a little more carefully.
Yes. Big endian was "natural" and x86 was weird and awkward, and a niche low end design that woud never be connected to networks.
For example let's say I send a message to 1.2.3.4, the first router will decide what will be the next node based on the first number, the next one on the second, the next on the third, etc... Because it is big endian, the first router only has to read the first number to do its job, if it was little endian, it would have to read the entire address fist.
Of course, it is a detail, I mean, the words "little/big endian" is a parallel to the the pointless fights in Gulliver's travels. But even if it could have gone either way, for IP, big endian is more natural.
I've designed several transport protocols (don't ask) - and they are really just minor riffs on TCP.
if aliens had a fault-prone wire they wanted to send a message across over some distance - it seems quite likely they would end up with TCP
There actually was software in the 1970s, and earlier.
* University of Toronto, ON, Canada: HEAVY math; queuing theory; no computer lab, no mention on any specific stack or technology
* University of Athabasca, AB, Canada: No math; discussion on OSI Layers, TCIP/IP, SMTP, Ethernet; gateways routers switches, virtualization; lots of fun computer labs. Not technology specific - it wasn't doing Cisco certs or anything. But good working understanding of what's happening in networking world.
I always felt one university taught working software engineers; other university taught the dozen people worldwide who need to create next IPv8 :D
What are you talking about? It was a three year argument based extremely heavily on prior knowledge
Why does everyone think that just because they don't know what craft went into something, there wasn't any?
(This is not to downplay the work of the pioneers who discovered these foundational concepts; just to point out that they used less sophisticated mathematical tools)
> Measure theory has played an important role for domains in modeling probabilistic computation.
[1] https://en.wikipedia.org/wiki/Connection_Machine#Designs
This is incredibly off-base. There was a huge effort to force an OSI-designed networking protocol stack that was designed by a committee of government bureaucrats and big blue sales engineers. It was a total disaster, but the vast amount of resources that were dedicated to forcing the OSI memes was in the billions of dollars. Large amounts of actual physical hardware were produced conforming to protocol standards nobody doing anything real actually wanted to use because a lot of government agencies required all network equipment to be compatible with the OSI protocol stack.
TCP, UDP, and the modern routing protocols (BGP, OSPF, etc) and their associated address resolution systems were not an arbitrary choice -- they represented orders of magnitude level improvements over the government-backed OSI standards and getting them to succeed was the product of intense collective effort of some of the most brilliant minds of the past century.
TCP/IP was in no way an technical improvement over OSI
Nothing has stood up to as much scrutiny and scale as TCP/IP. The simplicity is definitely an important part of it. Protocols that are used by trillions of devices need to be simple, and the equipment used to switch and route their traffic have to defer as much handling of state to the clients as possible. The more state that routers have to maintain, the less reliable they will be. TCP/IP accomplished that and that's why it was better.
Edit: Note that the frontier of the field will always be extremely hard no matter what time you live in. The reason is that things will be poorly understood and written, there will be no good textbooks or explanations, you have to trudge through all that often without anyone to help you understand things or correct you. It took centuries for calculus to become as easy as it is today.
There's a large trench between what people expect and what reality is here.
See https://slatestarcodex.com/2016/11/17/the-alzheimer-photo/
Now, there's half a mile of land for people to safely and easily scout through knowing they can always setup camp at the new established camp and work back towards previous understanding or work from previous understanding to the new camp. There's often a lot of low hanging fruit to be had here once a leap, not small incremental step into the frontier, has been made.
it's easy to use, but it's (IMO) even harder to understand correctly than before. I'm referring to a mathematical-level understanding; i.e. you could re-invent it because of how well you undesrtand all of it.
For instance, I can't take a derivative without the rules in front of me, though the concept of derivatives is simple.
I think that during the 19th century when it (along with logic) was being formalized they decided to throw away the old original ways to think about it. This ends up making it really hard to understand in exchange for making it "formally sound" and "user friendly".
"Introduction to Calculus and Analysis" Volume 1
Epsilon Delta is not our definition of limits, it's the definition of the derivative that uses limits as the "backend". But even using infinitesimals you can use the epsilon-delta definition of the derivative.
Just out of curiosity, in nonstandard analysis is there an equivalent of Lebesgue integral?
IIRC, even Newton was at least a bit skeptical of the validity of his method of fluxions, even going so far as to formulate his Principia in terms of (nearly impenetrable IMO) arguments from classical geometry instead, and the non-rigorous application of related ideas led even the best mathematicians to questionable conclusions at times (e.g., Euler's argument that 1 + 2 + 4 + ⋯ = -1, which may or may not have influenced computer science in terms of two's complement arithmetic).
As for abstraction as a source of seemingly artificial difficulty in modern mathematics, from the introduction to Courant's Differential and Integral Calculus, the first edition of Introduction to Calculus and Analysis[2],
The presentation of analysis as a closed system of truths without reference to their origin and purpose has, it is true, an aesthetic charm and satisfies a deep philosophical need. But the attitude of those who consider analysis solely as an abstractly logical, introverted science is not only highly unsuitable for beginners but endangers the future of the subject; for to pursue mathematical analysis while at the same time turning one's back on its applications and on intuition is to condemn it to hopeless atrophy.
For similar arguments that over-reliance on formalism begins far earlier in the modern mathematical curriculum, see Feynman's New Textbooks for the "New" Mathematics [3], in which he discusses his frustrations as a working (theoretical!) physicist reviewing grade school textbooks.
As a partial counterpoint, I personally often have an easier time understanding the more abstract treatments. For example, I struggled with the traditional presentation of multivariable calculus in terms of "physically meaningful" differential operators until working through the first couple books of Spivak's Comprehensive Introduction to Differential Geometry after-hours, at which point everything sort of clicked. Had my intro (college) calculus course not coincidentally been taught by a differential geometer with a habit of presenting some of the basic ideas as asides, I may have never made it any further in the field (in terms of learning; I work in software, not maths).
Nevertheless, I'd never propose Bourbaki as a good model for elementary education!
Revised (Introduction to…) editions of Courant's calc textbooks are particularly noteworthy in this respect; to me, at least, they strike a very good balance between classical and modern formalisms, and between applications to pure and applied mathematics.
As for the application of "general abstract nonsense" to computer science and engineering, I have no doubt Courant would be pleased, with the applications if not in their presentation, as the interplay between pure mathematics and its applications was always an important subject to him (see also the introduction to his [and, nominally, Hilbert's] Methods of Mathematical Physics [4], the address he gave on variational methods in PDEs [5], often cited as a foundational work in finite element analysis, and, well, pretty much the entirety of What is Mathematics?[6]).
[1] https://en.wikipedia.org/wiki/Nonstandard_analysis
[2] https://onlinelibrary.wiley.com/doi/pdf/10.1002/978111803324...
[3] http://calteches.library.caltech.edu/2362/1/feynman.pdf
[4] https://onlinelibrary.wiley.com/doi/pdf/10.1002/978352761721...
[5] https://www.ams.org/journals/bull/1943-49-01/S0002-9904-1943...
x + y + z = 0
dx/dy * dy/dz * dz/dx = -1
that make no sense if you don't know epsilon-delta calculus.
You can use infinitesimal analysis but that's a completely different thing that you probably won't enjoy if you don't think epsilon-delta is straightforward.
https://en.m.wikipedia.org/wiki/Smooth_infinitesimal_analysi...
The other surprising thing to me was that it didn't really resemble modern algebra at all. As a former math student I think it's easy to create a mental model of math history where when new fields are created they resemble the modern incarnation. But when you actually look at the primary founding texts its clear the ideas and notation are pretty unrefined at least compared to today's standards.
I've just started reading it and Petzold claims all you need is a decent grasp of high school mathematics.
Glad to see I'm not the only one...
Today Grace Hopper's "compiler" wouldn't merit the name, it's just a linker loader, what's the big deal? Well the big deal was nobody had actually programmed the computer to help them program the computer before. A huge sub-discipline of computer science simply didn't exist.
Consider another discipline, metrology. Pioneers in metrology weren't doing advanced physics like you would see in a metrology lab today, they just had the insight that it sure is easier if everybody agrees how much corn this is, so they used prototypes, which is pretty much the simplest strategy but it's already a huge improvement on nothing at all. It took until this century for the last prototype (the Kilogram) to be replaced. On the route there those prototypes got a lot more sophisticated, and we learned a lot more about what it actually means to have a certain amount of a thing, so metrology got much harder.
Amusingly, that failure so drove me to learn computer science that I'm now an expert, but I often get stuff like order calculations wrong because they don't correspond well with actual computer performance.
Prof. Tom Leighton is an incredible teacher who teaches the intuition before the theory.
I went to a college in Boston in early 2000s for my CS degree and it was undergoing extra ABET accreditation to put it in line with the engineering programs. The prior year has mostly algebra based course work but due to the change: all our math (including physics) was switch to calculus based just like the other engineering programs. And the theory courses got more in depth.
So if I had to guess based on my personal experience I'd say added rigor is possibly due to the field becoming less like a free-for-all and more like engineering.
In other words, knowing why something works vs just experimenting until you stumble upon something that works.
I've always appreciated a B.Sc. or M.Sc. in Computer Science as the academically rigorous cousins of Associate degrees, B.A., and bootcamps. You can get a job with both types of education but one understands the theory behind things far better.
Edit: Not sure if it is like this globally so just as an FYI... B.Sc. and M.Sc. are Bachelor and Master of "science" degrees where as B.A. is in the Liberal Arts. In the US you have CS degrees in both. The B.A. is more well rounded but the B.Sc. is more rigorous in theory and math.
In neither case is it a matter of theory vs practice. It is that the mechanics used by theorists is a lot more difficult than a few decades ago.
Actual software development becoming like engineering, which seems counter to my experience, is a different issue.
In my experience software veers away from engineering because as soon as something is standardized enough to not be novel, it’s completely captured by a library or service or something and is a solved problem. The new software is always doing something new. And there are no lessons learned, except, ironically, at the deep theory level.
My undergraduate degree was in math, and I switch to CS for graduate work because math got too hard.
They’re remarkably different in difficulty.
My friend in complexity is clearly a mathematician. My friend who is an expert in random algorithms is doing a lot more throwing darts at a dartboard with enough theory chops to make his papers interesting.
I studied CS theory and modeling in university and my degree was effectively a math degree. Without the math and analysis piece I don’t think the theory ever would’ve been intuitive.
This isn't an annoyance like back-button breakage. It's a design issue with a very easy fix that makes it impossible to read this for (at least) some people
Take NP-Complete for instance. We know a problem is NP-Complete if we can do a Karp Reduction from another NP-Complete problem and also prove the problem is in NP. Sure, that's fine. But how was the first NP-Complete bootstrapped? Well, using automata and generalized turning machine languages! You can use NP-Complete as a concept at work, and never touch the original proof using a non-determistic turning machine language.
That's at least one course worth of material to teach in order to get students to understand automata. To me: that's a complex approach to a simple question: what can we compute? We have to invent a series of automata with increasing complexity and corresponding theories/proofs. I don't think it's bad, it's just the nature of the problem!
Till a few years ago, undergrads could contribute to CS theory research, whereas in math only senior grad students can do that.
What the article is saying is that CS theory is slowly moving towards the latter model, as more work is done and the low-hanging fruits are picked off.
The article seems to focus on complexity theory, but I couldn't think of any from that sub-field. My first thought is the Paxos algorithm for distributed consensus [1], which definitely has a reputation of being difficult to understand, and fits under the Theory umbrella.
[1] https://en.m.wikipedia.org/wiki/Paxos_(computer_science)
Disclaimer: I'm a software engineer who doesn't understand Paxos.
However, because my education/training has not been part of an institution, I do feel like I am on the outside of understanding when it comes to wrangling the lightning inside the rocks we work on day in/day out. I've been both DevOps (helpdesk jockey to admin) and dabbled in frontend work, but mostly fell into those positions and grew into them.
Couldn't tell you how to work with Kubernetes or Docker, but have been following discourse on here enough to understand how they are useful for big stuff. I used PuTTY back in HS to work on a backend internship, but have no clue why it works. I have made at least 2 programs still running internally at a big real estate tech company, but cannot deploy my own apps on my own computer.
Is this disconnect with deeper Computer Science theory just my issue as a visual and kinetic learner? Is the understanding of modern technology only suitably captured in a classroom setting that I do not have access or time for?
No one wants to admit that things were probably better when we ran our own infrastructure and bought hosting at fixed pricing, because they're busy making money off of the new and overly-complex "utility priced" cloud hosting solution model to hosting web sites and apps, and because the learning curve for their competition is now more steep, reducing the threat to their profit pipelines... There, I said it.
These days people have a huge problem with getting to the point in speech and in writing. If you put the premise up front, it allows people to get it an move on, or to argue with you online more easily without reading the elaboration below it.
There is usually a reason why software and hardware is made, to solve a specific problem, or to solve a group of problems, yet modern-day engineers don't see the importance of putting the detail about the problem(s) that their tools solve foreword FIRST AND FOREMOST before gushing about how to use their tools. A lot of the time they don't put the premise first because it's an ugly solution, or in reality simply useless, or based on being costly, and usually just too damn overly-complicated to really work consistently and accurately.
We also have marketers, managers, and sales people working to promote ideas without any real understanding about the reason why those things were created. Many people simply don't care as long as their share values increase or if they make a paycheck, so there's even more of a barrier to meaningful answers to why in the he|| things exist, to determining real meaningful fixes to modern-day problems, and to why certain solutions are different than other things used to solve already over-complicated IT problems.
Life is better when it's more simple, simplifying things frees up time to innovate beyond just ideas that are geared towards making profit. The world would be a far better place if we began a shift towards bringing technology back down to earth, and if everyone would stop chasing the annual "tech leader supreme monopolistic empire douchebag" awards.
:|
Kubernetes will immediately make sense if you take a serious Distributed Systems class.
I have some books on both OS and Distributed Systems (gotta love goodwill finds), and appreciate the pointer towards where I can deep delve on how these work at a deeper level :)
Instead, education became weaker :-(
See following link for foundations of computer Science:
Now, complex neural network architectures are available to all. Alas, simply gaining that access does not in any imply deeper understanding of what is occurring under the hood. Perhaps the higher technical demands is simply a byproduct of the more complex "off-the-shelf" solutions and the need to do more than simply pip install, point, and click?
NNs are not a hard thing to understand, it's just regression -- there's parameteric and non-parametric. And NNs are, just like any generic approximator algorithm, a largely non-parametric method. The lack of understanding of even what a parametric method is, in CS, is very telling: NB. it has nothing to do with the final model having parameters. It is whether the method assumes a parametrised distribution of its input data. Non-parameteric methods are well-understood, they aren't magic, and they aren't very hard to characterise.
Rather, it is exactly in those areas where compu-sci people are most qualified that the mathematics gets the hardest. Much of the low-hanging fruit has been picked (Turing, et al.) and today comes the hard part of the thorniest problems.
Having done my PhD work on (Bayesian) nonparametric methods I'm struggling to parse this.
What is the input data? Just the explanatory (independent) variables? Both explanatory and response (dependent) variables? Are we talking about a joint or conditional parametric distribution?
Many parametric methods (e.g. OLS regression) make no assumption about the distribution of the explanatory variables. Many "nonparametric" methods do make parametric assumptions about the conditional distribution of the response variable(s) conditioned on the explanatory variable(s) (e.g. GP regression).
I don't see how this works as a classification for whether a method is "nonparametric" or not.
If the parameters of the predictive model are a weakly compressive function of the dataset, then your method is non-parametric. If your parameters are extremely compressive it's parametric. Subject to both being low-loss models of the data.
Why? Well a non-parametric method is basically one which "uses the data points as its statistical model"; and a parametric method fits the data to a prior low-parameterised model.
Eg., linear regression essentially fits the data to a normal distribution = parametric on the mean/std, ie., pdf(Y|X) = N(ax +b, stdev). You fit (a,b) and thus essentially are just "finding a mean".
Eg., knn just remembers the dataset itself.
So there's a scale from "linear regression to knn", ie., Weights = (Mean, Stdev)... to Weights = (X, Y).
The terms parametric and non-parametric are fairly overloaded, so this way of characterising the distinction may either improve or worsen that.
Either way, my point is that NN model with a very high parameter count is essentially best analysed as KNN on a weakly compressed feature space. In that sense it is an incredibly obvious and simple algorithm.
Incidentally, NN can just be linear regression or KNN if you set it up appropriately. So NN is an alg. which runs "from knn to linear regression" depending on, eg., activation-fns, how hard you regularise it, etc.
TL;DR: It's a way to multiply n-digit integers in time O(n log n * log log n) time, developed in the early 70s, using DFTs in the ring Z mod 2^k + 1, with a slightly clever choice of k. Since the runtime was so tantalizingly close to O(n log n), it fueled speculation that O(n log n) was the optimal runtime. This bound was finally proven in 2019: https://hal.archives-ouvertes.fr/hal-02070778v2