recentpopularlog in

mcherm : computerscience   131

« earlier  
Mathematician Solves Computer Science Conjecture in Two Pages | Quanta Magazine
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
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
Several discoveries made this year (by surprisingly young researchers and one amateur).
math  computerscience  via:HackerNews 
december 2018 by mcherm
An Introduction to Cache-Oblivious Data Structures
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
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
My Biased Coin: Cuckoo Filters
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
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
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
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
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
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
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
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
Invertible Bloom Lookup Tables
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
The Scientific Case for P≠NP » Shtetl-Optimized
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
Compatibility is Not Transparency: VMM Detection Myths and Realities
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
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
A nice diagram for explaining the business value of idempotency.
computerscience  programming  datavisualization  via:HackerNews 
may 2013 by mcherm
Computer Science Blows My Mind
Some amazing things you can learn from computer science.
math  computerscience  via:reddit 
may 2013 by mcherm
In Search of an Understandable Consensus Algorithm: Raft
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
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
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
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
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
Magic: The Gathering is Turing complete - Boing Boing
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
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
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
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
We [PyPy] need Software Transactional Memory
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)
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
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
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
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
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
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 ?
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)
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)
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
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
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
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
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
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
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
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
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 What to know before debating type systems
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
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.
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
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
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)
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?
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
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 
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
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
Of Geeks and Girls - Science Notes 2009
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
« earlier      
per page:    204080120160

Copy this bookmark:

to read