andrewp123

I don’t know how any experiment like this could be taken seriously. Your action could change 15 minutes apart if you feel like having sugar, if the guy felt intimidating or not, if the last thing he said seemed friendly or if his facial expression was off at the very end, etc.

There must be a better way of judging the validity of a social experiment using first principles. There’s a huge psychological side that people completely ignore.

Algorithms are graphs, data structures are graphs, networks are graphs, relationships are graphs.

Let’s use text to describe everything!

I’m not sure how interesting this is - of course rotation causes the paths to differ and become measurable.

I’ve been wondering about sending photons away from earth and having their paths bend due to gravity (and later have them interfere). That would be interesting because GR would be involved.

I was thinking of creating something like this but centered around posting one’s intuitions on research, instead of the papers themselves (which are hard to read, even the list of titles are hard to parse). But researchers are afraid to say anything stupid and would prefer saying nothing at all.

It’s a hard problem but could be a good platform for research discussions considering none exists today. Best of luck.

I just wanted to comment on how good the homepage is - it's immediately clear what you do. Most people working with "combinators" would feel a need to use lots of scary lingo, but OP actually shows the simple idea behind the tool (this is the opposite take of most academics, who instead show every last detail and never tell you what's going on). I really appreciate it - we need more of this.

The word dynamic was popular in naming around that time - dynamic programming is another example (1950s).

Somehow just by internalizing the old meaning of the world “dynamic”, I feel I have a better idea of what the world felt like back then.

A powerful method in math is to assume the thing you're looking for is continuous, in which case you can write it F(n) = a0 + a1 n + a2 n^2 + ... .

You can solve Fibonacci by writing it as

a0 + a1 n + a2 n^2 + ...

= a0 + a1 (n-1) + a2 (n-1)^2 + ...

+ a0 + a1 (n-2) + a2 (n-2)^2 + ...

Expand terms, then match the n, n^2, n^3 etc terms and solve for a0, a1, a2, etc. This works in solving differential equations too - it's called "Method of Frobenius" (easier in diffeq because you don't have to do annoying binomial coefficient math).

I can't imagine you believe P=NP.

Always a bad idea to destroy musical instruments.

I just tried finding a good resource and I can’t. All of them are mile long page scrolls… I don’t know how they have so much stuff to spew. Qiskit had amazing lessons with cool illustrations (although they did spew at the end) but I can’t even find that anymore on their site.

Don’t worry though, even the professional researchers I’ve worked with think it’s a waste of time. The field is screwed.

Here’s a quick explanation from me- The state |x> means you have some qubits that represent the number x. Say you want to represent the number 13, that just means you have |1,0,1,1>, it just means you have 4 qubits in this configuration (quits can be 0 or 1). It’s also written |13>. If you want the state “13 AND 14 AND 15” in superposition where qubits are both 0 and 1, that’s represented by |1,0,1,1> + |1,1,0,0> + |1,1,0,1>. It’s in that superposition and can interact with itself until you choose to measure it. When you do go to measure it, you might measure any of the values (you dont get to choose which). Maybe you measure 15, that means the state is now |1,1,0,1>, you just deleted all the terms that aren’t 15.

This is a full pic of Shor’s algorithm https://images.app.goo.gl/ZE5rDxHScm4LUqms6

If you look at the pic, main idea is the first layer of H’s creates the state sum_x=0…2^n-1 |x, 0>, then gate U turns that state into sum_x |x, f(x)>, then the measurements measure which f(x) you have, deleting all the terms that don’t have that f(x) in them, so for example if you measure that f(x) is 13, the state is now |0, 13> + |15, 13> + |30, 13> + |45, 13> + … This is the periodic state. Now that we have it we can just apply a gate that takes the QFT (finds the frequency, which here turns the state into roughly |15, 13>), and then measures it, giving the answer period=15.

Yep, they're essentially giant brute force machines. You can find the period of a function by passing all the inputs through it at once and destructively interfering the result.

Why is there a speedup in quantum, though? Why can't you just brute force classically? The answer is that whether quantum or classical, you can always build a hard-coded circuit that essentially swaps the time and space complexity - just make it so that for every operation you were doing in time, instead, every operation happens at its own place in space.

Quantum is special because it also takes the "log" of the space complexity b/c n qubits represent 2^n bits. So quantum lets you swap space with time and then take the log of time, lol. Superposition, interference, etc aren't really even needed in the explanation.

Correct - superposition doesn't fork the world - measurement does. And correct, you can't communicate with the other universe after the split has happened [1]. I'm glad you mentioned that quantum computers can't solve NP-complete problems - my next blog post was going to be about why. Here's an overview of what I plan on saying:

A typical quantum algorithm like Shor's works by sending every possible input through a gate, and so you get every possible output out in a superposition. If you were to just measure that, you'd get a random result - so instead, you need to somehow interfere the output to get the actual result. You do this by taking advantage of the fact that the superposition is a periodic function and the amplitude repeats. This is literally the core assumption of the algorithm.(a common way of doing this using the QFT).

Every quantum algorithm requires some kind of structure in the output like this. Deustch's algo, dumb ones like Simon's algo, etc. NP-Complete problems have no structure to them, so even if you build a gate that creates the superposition you want, it's not possible to destructively interfere it to get an answer (I don't know how to prove that there's no structure to NP-Complete outputs - it just feels trivial, since they're only solvable in exponential time, so there must be an exponential amount of "structure" there).

---

[1] The only way to communicate with the other universe would be to try to use quantum mechanics with something like an entangled pair. But no information can be communicated through an entangled pair if all you just have 1 of the 2 particles! Measurement collapses a state nonlocally, and if you could somehow measure one particle and change the probability distribution of the other, you'd be communicating faster than light. The measurement genuinely changes the state and the amplitudes, but not in a way that the other person can detect. It's really interesting and leads to stuff like teleportation.

If you roll a regular coin without any quantum effects, every version of you will either see only heads, or only tails. You need quantum in order to make the choice nondeterministic.

It's a similar idea. The only difference is that if the event is quantum, the universe is choosing for you (otherwise the flip is deterministic).

If you want a more efficient way to practice, I’ve been working on https://deriveit.org/coding/roadmap#note-215. It’s LeetCode site that’s

-organized intelligently

-has simpler explanations than you find online

We’re super proud of our content and just recently 2 people have landed Amazon with us. People actually feel ready for interviews with us. Give it a go :).

Wow, shipfa.st boilerplate is really taking off!

DeriveIt has ~100 questions and ~40 lessons. It's up to you to decide how much practice you need, but users typically aren't limited by "not enough" practice problems.

Not sure if it's worth mentioning, but we made sure to cover all the ideas you learn from the Blind75 and NeetCode150. It's not like you're missing out - we're just:

- organized better

- higher quality solutions

(==> more efficient, hence not thousands of problems)

I've been working on a more effective leetcode site - https://deriveit.org/coding/roadmap.

The goal of our site is to teach smart people how to quickly master leetcode.

We put in a year's worth of thought to make things as simple as possible, and are super proud of our content. Recently, two people used our site to land Amazon. Check it out!

Always depressing to see a paper like this. I can almost guarantee one could make this whole thing into a two-page document with a clearer vision and followable to, well, anyone else.

The purpose of academic papers is to file a claim to ownership of ideas / progress. But it would be cool if in another place they published the intuitions they used to come up with the claim in the first place.

It’s really easy to come up with KMP. Just write an algorithm that searches for a substring p in string s. Make your algorithm efficient by sliding two pointers down s to find the biggest possible match, often called “sliding window”.

You want to grow the window as big as possible to match the substring. The data structure you naturally come up with to do checks efficiently here is the one you use in KMP.

I’ve been working with TypeScript and it’s literally wrong half the time. This code is 100% correct according to TS:

x: number[] = []

y: number = x[0]

The array type is missing information about the length of the array, and types are very often missing important information like this. Say you want to describe an array containing only odd integers - good luck.

Types are simply a heuristic for humans to try and remember vaguely what their code should do. If you want to do anything complex you need to abandon them anyway and use things like x!, and x as my_type. So designing around types seems like a bad idea.

You could do much better by abandoning text based programming languages and creating a visual programming language where you can zoom out and see what information gets passed where. The whole reason for types is to be a hack fix to the problem that we’re too zoomed in on their code and can only really reason about one function at a time given our crappy text-based programming languages.

You’re definitely onto something. The author starts a sentence with the words “In so far as”.

I think you're missing out on the time it takes to build the tree in the first place, which is O(M), equal the space complexity. People usually ignore this cost as a "preprocessing" factor, but it's a cost that's really there.

After this initial O(M) time and space cost, you do additional operations which only take up time, not space, so the claim Time >= Space holds here as well.

This is really cool. Would love to see a basic analysis of the physics - I know it's just basic angular momentum and torque. Are reaction wheels somehow intuitive and don't require you to think about these things?

In my opinion space limited solutions are not very interesting. Time complexity is always >= space complexity, so finding optimal time solutions is always more interesting. And we already knew the optimal time complexity. I appreciate a theoretical time vs space relation, but it doesn’t seem applicable to other areas.

It would be funny if one of the arrows in the visual on the side were missing. “Sorry, you can’t convert that.”

It seems their result has been out for almost a year now... https://arxiv.org/abs/2303.14605

I'm curious how this affects Traveling Salesman. I was under the impression that all NP-Complete problems take O(n!). Does this method improve it at all?

Very confusing to call it time travel when it has nothing to do with time…

This post really doesn’t say a lot. One sentence describes it: if people are incentivized to move towards each other they will, and if they’re not as much then they won’t.

This is a common practice I see among educators, make something overcomplicated so the audience feels they accomplished something at the end or learned something meaningful, even though it was extremely simple in the first place. You can always make more of something than there is.

Not this again.