**mcherm : computerscience**
131

Mathematician Solves Computer Science Conjecture in Two Pages | Quanta Magazine

22 days ago by mcherm

For 30 years the brightest minds in computer science tried this easy-to-explain problem and failed. The proof is beautiful and incredibly short (1.5 pages written out carefully; abbreviated fits in a tweet).

math
computerscience
via:reddit
22 days ago by mcherm

New Approach Could Sink Floating Point Computation

5 weeks ago by mcherm

There is ACTUALLY a credible alternative to IEEE 754 for floating point.

floatingpoint
programming
computerscience
via:HackerNews
5 weeks ago by mcherm

Quanta’s Year in Math and Computer Science (2018) | Quanta Magazine

december 2018 by mcherm

Several discoveries made this year (by surprisingly young researchers and one amateur).

math
computerscience
via:HackerNews
december 2018 by mcherm

History of the isomorphism between programs and proofs

december 2018 by mcherm

Dense reading, but to me quite fascinating.

math
computerscience
december 2018 by mcherm

An Introduction to Cache-Oblivious Data Structures

february 2018 by mcherm

Analyze data structures in terms of number of cache misses for cache size B (instead of the usual number of steps executed) and you get "cache oblivious" data structures, which are often 2x better in the real world.

computerscience
datastructures
programming
via:HackerNews
february 2018 by mcherm

Clever algorithm to determine whether or not two words are anagrams - math

june 2017 by mcherm

Multiply the primes corresponding to each letter. If primes are assigned in order of letter frequency, the integer might not overflow and it might be efficient.

algorithm
math
via:reddit
computerscience
june 2017 by mcherm

Scott Aaronson's Survey of everything about P=NP (PDF)

january 2017 by mcherm

116 page long paper which is fairly readable and very comprehensive.

math
computerscience
computationalcomplexity
complexity
ScottAaronson
via:ScottAaronson
january 2017 by mcherm

The memory models that underlie programming languages

january 2017 by mcherm

I found this perspective rather insightful.

programming
computerscience
languages
via:HackerNews
january 2017 by mcherm

The Astounding Link Between the P≠NP Problem and the Quantum Nature of Universe — The Physics arXiv Blog — Medium

july 2016 by mcherm

I'm not sure how far to believe this; this summary leaves out too much.

physics
math
computerscience
via:HackerNews
july 2016 by mcherm

My Biased Coin: Cuckoo Filters

may 2016 by mcherm

An alternative to the Bloom Filter which they claim works better (in practice, although it fails in theory) as long as the universe of possible values is a few billion or less.

programming
datastructures
algorithms
computerscience
probabilisticcomputing
bloomfilter
may 2016 by mcherm

Leapfrog Probing

may 2016 by mcherm

An implementation of a lock-free concurrent hashtable -- and the writeup is REALLY excellent. (Read the whole chain of previous articles to get the entire story.)

concurrentprogramming
concurrency
parallelprogramming
hash
programming
computerscience
may 2016 by mcherm

Scott Aaronson Answers Every Ridiculously Big Question I Throw at Him - Scientific American Blog Network

may 2016 by mcherm

Lots of questions about quantum computing explained incredibly well. Also a great explanation of why P=?=NP is such an important problem.

ScottAaronson
computerscience
quantumcomputing
ScientificAmerican
via:SlateStarCodex
quantummechanics
may 2016 by mcherm

The 8000th Busy Beaver number eludes ZF set theory: new paper by Adam Yedidia and me

may 2016 by mcherm

They constructed an 7918-state 2-symbol Turing machine which (provably) cannot be proved to stop or not stop using standard ZFC set theory (and independent of the Axiom of Choice).

math
computerscience
computationalcomplexity
ScottAaronson
via:reddit
bignumbers
may 2016 by mcherm

LL and LR in Context: Why Parsing Tools Are Hard

february 2016 by mcherm

A readable explanation of the limits of some parsing algorithms, mostly deriving from ambiguities in grammars.

parsing
computerscience
programming
via:HackerNews
february 2016 by mcherm

Computer scientists prove that a 40-year-old algorithm is optimal | Hacker News

june 2015 by mcherm

I say why things like heuristic and probabilistic algorithms are likely to be really, really important in computer science.

computerscience
mypostings
blogworthy
via:HackerNews
june 2015 by mcherm

Longstanding problem put to rest | MIT News

june 2015 by mcherm

If P != NP then the standard (quadratic) algorithm for finding the edit distance between two strings is (asymptotically) optimal.

computerscience
algorithms
via:HackerNews
june 2015 by mcherm

The strange fate of a person falling into a black hole

may 2015 by mcherm

The current thinking on falling into a black hole. The outside observer says you were stretched out and burned up before crossing the event horizon; the person falling thinks they passed the event horizon just fine; the universe conspires to keep them from comparing notes, and part of the universe conspiring MIGHT involve computational complexity.

physics
complexity
computerscience
via:HackerNews
may 2015 by mcherm

A Few Thoughts on Cryptographic Engineering: Zero Knowledge Proofs: An illustrated primer

november 2014 by mcherm

A nice high level summary of zero knowledge proofs.

cryptography
computerscience
via:HackerNews
november 2014 by mcherm

Invertible Bloom Lookup Tables

august 2014 by mcherm

A bloom filter where you can list the values as long as the number of values is small enough... then when it gets large you stop being able to until it shrinks down again.

computerscience
datastructures
probabilisticcomputing
programming
august 2014 by mcherm

Just LOOK at the humongous type that Hindley-Milner infers for this tiny program! - What I cannot create, I do not understand.

august 2014 by mcherm

A very readable explanation of an odd corner of Hindley-Milner: exponentially large types.

via:HackerNews
computerscience
types
august 2014 by mcherm

What should be included in a freshman 'Mathematics for computer programmers' course? - Mathematics Educators Stack Exchange

april 2014 by mcherm

Big list of mathematical topics that are useful in programming.

math
computerscience
april 2014 by mcherm

The Scientific Case for P≠NP » Shtetl-Optimized

march 2014 by mcherm

A really good explanation for why they believe (without proof) that P != NP. There are many known problems where two different kinds of reasoning show that below a certain value of a parameter it's in P and above a certain value it's in NP... and they happen to be the exact same value. What a coincidence, unless there's a reason for it.

philosophyOfScience
math
computerscience
computationalcomplexity
via:ScottAaronson
ScottAaronson
philosophyOfMath
march 2014 by mcherm

A Few Thoughts on Cryptographic Engineering: Cryptographic obfuscation and 'unhackable' software

february 2014 by mcherm

A fairly good explanation of the recent developments in securely obfuscated programs.

cryptography
computerscience
math
via:HackerNews
february 2014 by mcherm

Laurence Tratt: Parsing: The Solved Problem That Isn't

february 2014 by mcherm

A survey of the current state of grammar parsing.

computerscience
languagedesign
parsing
via:reddit
february 2014 by mcherm

Compatibility is Not Transparency: VMM Detection Myths and Realities

january 2014 by mcherm

In theory, a virtual machine can always fool software running on it. In practice, programs can detect being in even a clever and malicious virtual container if they insist on running on reasonably recent hardware and talking to the outside world.

via:HackerNews
virtualization
virtualmachine
computerscience
january 2014 by mcherm

Voevodsky’s Mathematical Revolution | Guest Blog, Scientific American Blog Network

december 2013 by mcherm

A fields medalist says he's connected a few fielkds in math and thereby made computer proofs easier. He predicts large numbers of mathematicians collaborating using automated proof systems.

math
computerscience
proof
via:HackerNews
december 2013 by mcherm

Idempotency Concept Roadmap Prototype

may 2013 by mcherm

A nice diagram for explaining the business value of idempotency.

computerscience
programming
datavisualization
via:HackerNews
may 2013 by mcherm

Big-O Algorithm Complexity Cheat Sheet

may 2013 by mcherm

A table of big-O values for common algorithms.

computerscience
programming
algorithms
via:reddit
may 2013 by mcherm

Computer Science Blows My Mind

may 2013 by mcherm

Some amazing things you can learn from computer science.

math
computerscience
via:reddit
may 2013 by mcherm

Raft: A more understandable consensus algorithm that is equivalent to Paxos : compsci

april 2013 by mcherm

I read and reviewed an article on a consensus algorithm.

mypostings
programming
computerscience
concurrentprogramming
via:reddit
april 2013 by mcherm

In Search of an Understandable Consensus Algorithm: Raft

april 2013 by mcherm

Proposes Raft, an algorithm for distributed consensus that is simpler than Paxos. The algorithm design was motivated by "understandability" and I feel it achieves that.

computerscience
algorithms
algorithm
via:reddit
april 2013 by mcherm

High Scalability - High Scalability - Cloud Programming Directly Feeds Cost Allocation Back into Software Design

january 2013 by mcherm

Interesting observation. We're used to Big-O analysis of time and memory constraints. But cloud computing introduces a new question: cost scaling -- which may have more practical importance than measurements.

cloudcomputing
computerscience
january 2013 by mcherm

Another Non-Argument in Type Systems: Laurence Tratt

october 2012 by mcherm

Any program written with dynamic types has an equivalent in a static type system which is written using generic types everywhere. Some programs that work in dynamic languages that would fail at compile-time in a static language. There is a useful duality here.

computerscience
types
via:HackerNews
october 2012 by mcherm

Bitcoins value is decentralization : Paul Bohm's Blog

october 2012 by mcherm

The key to why bitcoin is so effective is that it actually solved the Byzantine Generals problem by forcing the generals to spend computational resources and then accepting a consensus has been reached if more than half of the computational resources have been invested.

bitcoin
computerscience
via:HackerNews
parallellcomputing
concurrentprogramming
october 2012 by mcherm

The $5000 Compression Challenge

october 2012 by mcherm

Someone bet he couldn't create some smaller files that decompress into a big file picked by the bettor. He won, but the bettor wouldn't pay up.

programming
computerscience
hack
history
october 2012 by mcherm

Why Bloom filters work the way they do | DDI

september 2012 by mcherm

An excellent motivation for why Bloom filters work the exact way that they do.

programming
bloomfilter
datastructures
computerscience
probabilisticcomputing
via:HackerNews
september 2012 by mcherm

Magic: The Gathering is Turing complete - Boing Boing

september 2012 by mcherm

It shows that you can't REALLY ban Turing complete systems, they're just too easy to create by mistake.

CoryDoctorow
computerscience
games
gamedesign
september 2012 by mcherm

10 yr Old CS Problem Solved

july 2012 by mcherm

By asking questions of a superintelligence you can trick them into revealing information. By asking multiple superintelligences that can't talk to each other, you do better. But you can't do better if they can share quantum-entangled pairs.

computerscience
math
personal_net
via:HackerNews
july 2012 by mcherm

Two eggs puzzle

july 2012 by mcherm

Find the lowest floor you can safely drop an egg out of. You have 2 eggs.

computerscience
math
mathpuzzle
via:reddit
july 2012 by mcherm

research!rsc: Random Hash Functions

april 2012 by mcherm

It may be an April 1st posting, but this is an interesting idea. Since NAN values are not equal (even to THEMSELVES) perhaps they should generate a RANDOM value for their hash function.

via:HackerNews
computerscience
programming
hash
probabilisticcomputing
april 2012 by mcherm

Scott Aaronson - Quantum Computing Promises New Insights - NYTimes.com

december 2011 by mcherm

An explanation of some basic ideas in quantum computing including why it is important.

computerscience
quantummechanics
quantumcomputing
via:ScottAaronson
ScottAaronson
nytimes
december 2011 by mcherm

We [PyPy] need Software Transactional Memory

august 2011 by mcherm

Armin: PyPy has a GIL; to get rid of it we needs STM. Can’t do fine-grained locks like Jython because it’s hard to do; CAN do STM surprisingly easily because PyPy does whole-program transformations with ease. So he proposes trying to add STM to PyPy. He guesses 10x slowdown, perhaps 2x slowdown with serious optimization (wow… realistic expectations!) I think this is the sort of experiment that PyPy exists for, and is WELL worth trying.

via:reddit
ArminRigo
stm
pypy
parallellcomputing
threading
programming
computerscience
concurrency
concurrentprogramming
august 2011 by mcherm

Why Events Are A Bad Idea (for high-concurrency servers)

august 2011 by mcherm

Contrary to claims, threads > events. The 2 are duals and should be equal. Threads map to our brains better. BUT, most thread libraries/compilers suck; we made a good one to prove it's possible. Cooperative threading and compiler hints are essential.

concurrency
programming
architecture
scalability
research
asynchronous
threading
computerscience
via:reddit
august 2011 by mcherm

Anybody with distributed computing experience here? : compsci

july 2011 by mcherm

I point out that if your computation takes 10^10 years then it doesn’t help to run it in EC2.

mypostings
computerscience
via:reddit
july 2011 by mcherm

Complexity on Forbidden-Minor Planets? « Gödel’s Lost Letter and P=NP

june 2011 by mcherm

Certain things that are hard (NP complete) on graphs in general become easy (polynomial) on graphs that lack certain sub-graphs (technically, certain "minors"). That's interesting.

math
computerscience
via:DickLipton
june 2011 by mcherm

Mathematical Recreations

june 2011 by mcherm

A playful Martin Gardener style essay on Turing machines and model trains.

math
computerscience
via:HackerNews
june 2011 by mcherm

Blog: November 30, 2009: Why Object-Oriented Languages Need Tail Calls â€“ projectfortress Community

june 2011 by mcherm

An essay arguing for tail calls. What I found fascinating was not the tail call argument, but the way it demonstrated a deep connection between TRUE object encapsulation (of the kind rarely seen in Java and C++) and recursion.

via:HackerNews
programming
functional
oop
fortress
languagedesign
computerscience
blogworthy
recursion
june 2011 by mcherm

Wang tile - Wikipedia, the free encyclopedia

march 2011 by mcherm

Primrose-style aperiodic tilings which can encode the halting problem -- fun stuff!

math
computerscience
march 2011 by mcherm

ckwop comments on How can I know which parts in the code are never used ?

january 2011 by mcherm

About the halting problem and why it's more of a theoretical problem than a practical one.

computerscience
via:reddit
mypostings
january 2011 by mcherm

Vanish: Increasing Data Privacy with Self-Destructing Data (pdf)

january 2011 by mcherm

How do you build something that will reliably destroy your data after a time limit, even if the FBI grabs your hard drive? Encrypt with a random key, then Shamir secret share the key to a P2P network but without guaranteeing long-term storage.

computerscience
cryptography
privacy
encryption
p2p
via:reddit
blogworthy
january 2011 by mcherm

paxos_made_live.pdf (application/pdf Object)

january 2011 by mcherm

The Paxos algorithm allows a group of cooperating servers to agree on a value even in the face of failing nodes and network failures. Google engineers built a real-world implementation of this which stores a reliable log (useful to build a reliable database). Interesting research learnings.

research
google
GoogleAppEngine
threading
programming
computerscience
january 2011 by mcherm

The surprising usefulness of sloppy arithmetic

january 2011 by mcherm

Making computer circuits that are not 100% accurate. According to this article, it allows much greater computation on the same amount of silicon, and it's perfect for tasks like video processing.

probabilisticcomputing
computerscience
hardware
via:reddit
january 2011 by mcherm

Yacc is dead: An update

december 2010 by mcherm

More details about that parsing technique that uses "the derivative of a grammer". By this point, they have a working example in highly readable Scala code that's less than 100 lines long, along with some good analysis of the runtime complexity of the approach. It sounds amazingly good.

programming
computerscience
parsing
algorithms
via:HackerNews
december 2010 by mcherm

YACC is Dead: the derivative of a regular expression

december 2010 by mcherm

This paper introduces the odd concept of the derivative of a regular expression and discusses how to use it to build a really cool parser in a language like Haskell or Scala.

programming
computerscience
scala
via:LambdaTheUltimate
parsing
december 2010 by mcherm

First improvement of fundamental algorithm in 10 years

september 2010 by mcherm

Someone has found a truly new algorithm for the "max flow" problem, which is apparently a commonly recurring optimization problem. There is, however, no actual paper I could find telling how it actually works.

algorithms
programming
computerscience
math
via:HackerNews
september 2010 by mcherm

Getting to the Bottom of Nothing At All: One Div Zero

august 2010 by mcherm

A lucid explanation of the value "bottom" (in type theory) and examples of how it is used, written so a Java programmer could follow it.

programming
computerscience
types
typesystem
functional
via:JamesIry
JamesIry
august 2010 by mcherm

The Easiest Hard Problem » American Scientist

august 2010 by mcherm

Picking teams for baseball is an NP complete problem. And NP complete problems appear to have a sort of "phase transition".

math
computerscience
complexity
via:reddit
august 2010 by mcherm

Shtetl-Optimized: Eight Signs A Claimed P is not NP Proof Is Wrong

august 2010 by mcherm

The evidence that Scott Aaronson used to quickly evaluate a proposed proof of P!=NP and very rapidly reach enough confidence to bet his house on it.

ScottAaronson
computerscience
math
complexity
proof
philosophy
august 2010 by mcherm

Putting my money where my mouth isn’t » Shtetl-Optimized

august 2010 by mcherm

Now that's one way of making your point. Scott Aaronson (a well-known blogger in complexity theory) wants to show how sure he is that the newly revealed proof that P!=NP will have flaws. But he doesn't have time to find the flaws. So he literally bets his house on it.

ScottAaronson
math
skepticism
computerscience
complexity
proof
philosophy
august 2010 by mcherm

Ovid at blogs.perl.org: What to know before debating type systems

august 2010 by mcherm

Read this to learn more about "type systems" than any other article of similar length that I have ever seen.

programming
via:reddit
languagedesign
types
computerscience
languages
august 2010 by mcherm

http://djm.cc/bignum-results.txt

july 2010 by mcherm

Goal: write the C program that gives the biggest possible output (assuming arbitrary precision integers) with the restriction that the program be 512 characters or less.

computerscience
programming
math
bignumbers
july 2010 by mcherm

RethinkDB - The database for solid state drives.

june 2010 by mcherm

Another "I'm hiring, and Gee, they're all Stupid!" post. Points out that it's not unfair to ask basic CS questions "Because they’re part of a core body of knowledge taught in any undergraduate curriculum worth its salt, and because in some form or another, they came up in our daily work."

hiring
softwaredevelopment
computerscience
june 2010 by mcherm

SNA Projects Blog : Beating Binary Search

june 2010 by mcherm

Better than binary search: interpolation search is log(log(n)) if the array is randomly but uniformly populated.

programming
computerscience
algorithms
june 2010 by mcherm

Worst Case Complexity « Gödel’s Lost Letter and P=NP

june 2010 by mcherm

A possible alternate means for analyzing algorithms: based, not on WORST case (which is unreasonably bad) or average case (which may be too good) but on an opponent with only polynomial-time resources available.

complexity
computerscience
math
algorithms
via:DebasishGhosh
june 2010 by mcherm

NP-complete Problems and Physical Reality (PDF)

april 2010 by mcherm

A survey paper questioning what properties of the universe (including mostly theories NOT believed to be true) might be used to produce faster computation than a classical or quantum computer.

computerscience
ScottAaronson
computationalcomplexity
physics
quantum
via:reddit
april 2010 by mcherm

A Neighborhood of Infinity: What does topology have to do with computability?

april 2010 by mcherm

You can represent real numbers on the computer... actual real numbers, not approximations like floats. But some of the obvious approaches fail. And when you do, you get interesting results, like all functions are continuous.

math
computerscience
programming
via:reddit
april 2010 by mcherm

Regular Expression Matching Can Be Simple And Fast

march 2010 by mcherm

A better approach to running regular expressions -- it does not have pathological cases that take exponential time.

algorithms
computerscience
programming
regexp
google
march 2010 by mcherm

Stevey's Home Page - Ten Challenges

february 2010 by mcherm

Some excellent books to read for a true programmer (or better yet, a computer scientist). Just to give a hint, it starts out with Godel, Escher, Bach. He (Steve Yegge) has written other top-10-book lists before, but this is the top 10 list of HARD books.

via:HackerNews
yegge
books
programming
computerscience
toread
february 2010 by mcherm

Null References: The Billion Dollar Mistake

january 2010 by mcherm

Hoare (inventor of Quicksort and other stuff) blames himself for inventing "null" and calls it a "billion dollar mistake".

programming
history
Hoare
computerscience
bug
via:HamletD'Arcy
january 2010 by mcherm

Laziness makes you think differently - Learning Haskell: Ruminations of a Programmer

december 2009 by mcherm

Some simple examples of the problems of laziness in a language.

programming
computerscience
functional
haskell
laziness
via:DebasishGhosh
DebasishGhosh
december 2009 by mcherm

Of Geeks and Girls - Science Notes 2009

december 2009 by mcherm

Another article with actual research on why there are so few women in computers. This one says that the ENVIRONMENT (such as excessively geeky room decorations) makes a huge (and measurable) difference.

gender
programming
computerscience
via:HackerNews
december 2009 by mcherm

Copy this bookmark: