"algorithms" entries

Four short links: 19 August 2015

Four short links: 19 August 2015

Privacy-Respecting Algorithms, Dealers Growing, Book Recommendations, and End of Internet Dreams

  1. Efficient Algorithms for Public-Private Social Networks — Google Research paper on privacy-respecting algorithms for social networks. From the overview: the models of privacy we’re landing on (nodes or edges in the graph are marked as “private” by a user) mean that enforcing these privacy guarantees translates to solving a different algorithmic problem for each user in the network, and for this reason, developing algorithms that process these social graphs and respect these privacy guarantees can become computationally expensive. The paper shows how to efficiently approximate some of the graph operations required to run a social network.
  2. Rise of Networked Platforms for Physical World Services (Tim O’Reilly) — the central player begins by feeding its network of suppliers, but eventually begins to compete with it. […] Over time, as networks reach monopoly or near-monopoly status, they must wrestle with the issue of how to create more value than they capture — how much value to take out of the ecosystem, versus how much they must leave for other players in order for the marketplace to continue to thrive.
  3. Book Recommendations from BLDBLOGWinslow memorably pointed out how farmers in the Sinaloa region of Mexico had been swept up into the cartel’s infinitely flexible method of production, and that, despite any ensuing role growing and harvesting marijuana or even poppies, the cartel offered them new jobs in logistics, not agriculture. “They didn’t want to be farmers,” Winslow said at Bookcourt, “they wanted to be FedEx.”
  4. The End of the Internet Dream (Jennifer Granick) — this is all gold. Something resonating with my current meditations: People are sick and tired of crappy software. And they aren’t going to take it any more. The proliferation of networked devices — the Internet of Things — is going to mean all kinds of manufacturers traditionally subject to products liability are also software purveyors. If an autonomous car crashes, or a networked toaster catches on fire, you can bet there is going to be product liability. […] I think software liability is inevitable. I think it’s necessary. I think it will make coding more expensive, and more conservative. I think we’ll do a crappy job of it for a really long time.
Comment
Four short links: 12 August 2015

Four short links: 12 August 2015

Economic Futures, Space War, State of Security, and Algorithmic Fairness

  1. Possible Economics Models (Jamais Cascio) — economic futures filtered through Doctorovian prose. Griefer Economics: Information is power, especially when it comes to finance, and the increasing use of ultra-fast computers to manipulate markets (and drive out “weaker” competitors) is moving us into a world where market position isn’t determined by having the best offering, but by having the best tool. Rules are gamed, opponents are beaten before they even know they’re playing, and it all feels very much like living on a PvP online game server where the referees have all gone home. Relevant to Next:Economy.
  2. War in Space May Be Closer Than Ever (SciAm) — Today, the situation is much more complicated. Low- and high-Earth orbits have become hotbeds of scientific and commercial activity, filled with hundreds upon hundreds of satellites from about 60 different nations. Despite their largely peaceful purposes, each and every satellite is at risk, in part because not all members of the growing club of military space powers are willing to play by the same rules — and they don’t have to, because the rules remain as yet unwritten. There’s going to be a bitchin’ S-1 risks section when Planet Labs files for IPO.
  3. Not Even Close: The State of Computer Security (Vimeo) — In this bleak, relentlessly morbid talk, James Mickens will describe why making computers secure is an intrinsically impossible task. He will explain why no programming language makes it easy to write secure code. He will then discuss why cloud computing is a black hole for privacy, and only useful for people who want to fill your machine with ads, viruses, or viruses that masquerade as ads. At this point in the talk, an audience member may suggest that bitcoins can make things better. Mickens will laugh at this audience member and then explain why trusting the bitcoin infrastructure is like asking Dracula to become a vegan. Mickens will conclude by describing why true love is a joke and why we are all destined to die alone and tormented. The first ten attendees will get balloon animals, and/or an unconvincing explanation about why Mickens intended to (but did not) bring balloon animals. Mickens will then flee on horseback while shouting “The Prince of Lies escapes again!”
  4. Algorithms and Bias (NYTimes) — interview w/Cynthia Dwork from Microsoft Research. Fairness means that similar people are treated similarly. A true understanding of who should be considered similar for a particular classification task requires knowledge of sensitive attributes, and removing those attributes from consideration can introduce unfairness and harm utility.
Comment
Four short links: 13 July 2015

Four short links: 13 July 2015

Improving Estimates, Robot Bother, Robotics Nations, and Potential Futures of Work

  1. Kalman Filteran algorithm that uses a series of measurements observed over time, containing statistical noise and other inaccuracies, and produces estimates of unknown variables that tend to be more precise than those based on a single measurement alone.
  2. Interview with Bruce SterlingSingapore is like a science fictional society without the fiction. Dubai is like a science fictional society without the science. […] Robots just don’t want to live. They’re inventions, not creatures; they don’t have any appetites or enthusiasms. I don’t think they’d maintain themselves very long without our relentlessly pushing them uphill against their own lifeless entropy. They’re just not entities in the same sense that we are entities; they don’t have much skin in our game. They don’t care and they can’t be bothered. We don’t yet understand how and why we ourselves care and bother, so we’d be hard put to install that capacity inside our robot vacuum cleaners.
  3. Japan’s Robot RevolutionFugitt said Japan’s weakness was in application and deployment of its advanced technologies. “The Japanese expect other countries and people to appreciate their technology, but they’re inwardly focused. If it doesn’t make sense to them, they typically don’t do it,” he said, citing the example of Japanese advanced wheelchairs having 100 kilogram weight limits. […] South Korea could be a threat [to Japan’s lead in robotics] if the chaebol opened up [and shared technologies], but I don’t see it happening. The U.S. will come in and disrupt things; they’ll cause chaos in a particular market and then run away.
  4. A World Without Work (The Atlantic) — In 1962, President John F. Kennedy said, “If men have the talent to invent new machines that put men out of work, they have the talent to put those men back to work.” […] Technology creates some jobs too, but the creative half of creative destruction is easily overstated. Nine out of 10 workers today are in occupations that existed 100 years ago, and just 5% of the jobs generated between 1993 and 2013 came from “high tech” sectors like computing, software, and telecommunications.
Comment: 1
Four short links: 30 April 2015

Four short links: 30 April 2015

Managing Complex Data Projects, Graphical Linear Algebra, Consistent Hashing, and NoTCP Manifesto

  1. More Tools for Managing and Reproducing Complex Data Projects (Ben Lorica) — As I survey the landscape, the types of tools remain the same, but interfaces continue to improve, and domain specific languages (DSLs) are starting to appear in the context of data projects. One interesting trend is that popular user interface models are being adapted to different sets of data professionals (e.g. workflow tools for business users).
  2. Graphical Linear Algebra — or “Graphical The-Subject-That-Kicked-Nat’s-Butt” as I read it.
  3. Consistent Hashing: A Guide and Go Implementation — easy-to-follow article (and source).
  4. NoTCP Manifesto — a nice summary of the reasons to build custom protocols over UDP, masquerading as church-nailed heresy. Today’s heresy is just the larval stage of tomorrow’s constricting orthodoxy.
Comment: 1
Four short links: 10 April 2015

Four short links: 10 April 2015

Graph Algorithm, Touchy Robots, Python Bolt-Ons, and Building Data Products

  1. Exact Maximum Clique for Large or Massive Real Graphs — explanation of how BBMCSP works.
  2. Giving Robots and Prostheses the Human Touchthe team, led by mechanical engineer Veronica J. Santos, is constructing a language of touch that both a computer and a human can understand. The researchers are quantifying this with mechanical touch sensors that interact with objects of various shapes, sizes, and textures. Using an array of instrumentation, Santos’ team is able to translate that interaction into data a computer can understand. The data is used to create a formula or algorithm that gives the computer the ability to identify patterns among the items it has in its library of experiences and something it has never felt before. This research will help the team develop artificial haptic intelligence, which is, essentially, giving robots, as well as prostheses, the “human touch.”
  3. boltons — things in Python that should have been builtins.
  4. Everything We Wish We’d Known About Building Data Products (DJ Patil and RusJan Belkin) — Data is super messy, and data cleanup will always be literally 80% of the work. In other words, data is the problem. […] “If you’re not thinking about how to keep your data clean from the very beginning, you’re fucked. I guarantee it.” […] “Every single company I’ve worked at and talked to has the same problem without a single exception so far — poor data quality, especially tracking data,” he says.“Either there’s incomplete data, missing tracking data, duplicative tracking data.” To solve this problem, you must invest a ton of time and energy monitoring data quality. You need to monitor and alert as carefully as you monitor site SLAs. You need to treat data quality bugs as more than a first priority. Don’t be afraid to fail a deploy if you detect data quality issues.
Comments: 2
Four short links: 2 April 2015

Four short links: 2 April 2015

250 Whys, Amazon Dash, Streaming Data, and Lightning Networks

  1. What I Learned from 250 WhysLet’s Plan for a Future Where We’re All As Stupid as We Are Today.
  2. Thoughts on Amazon Dash (Matt Webb) — In a way, we’re really seeing the future of marketing here. We’ve separated awareness (advertising) and distribution (stores) for so long, but it’s no longer the way. When you get a Buy Now button in a Tweet, you’re seeing ads and distribution merging, and the Button is the physical instantiation of this same trend. […] in the future every product will carry a buy button.
  3. A Collection of Links for Streaming Algorithms and Data Structures — is this not the most self-evident title ever?
  4. Lightning Networks (Rusty Russell) — I finally took a second swing at understanding the Lightning Network paper. The promise of this work is exceptional: instant, reliable transactions across the bitcoin network. But the implementation is complex, and the draft paper reads like a grab bag of ideas; but it truly rewards close reading! It doesn’t involve novel crypto, nor fancy bitcoin scripting tricks. There are several techniques that are used in the paper, so I plan to concentrate on one per post and wrap up at the end. Already posted part II.
Comment
Four short links: 26 March 2015

Four short links: 26 March 2015

GPU Graph Algorithms, Data Sharing, Build Like Google, and Distributed Systems Theory

  1. gunrocka CUDA library for graph primitives that refactors, integrates, and generalizes best-of-class GPU implementations of breadth-first search, connected components, and betweenness centrality into a unified code base useful for future development of high-performance GPU graph primitives. (via Ben Lorica)
  2. How to Share Data with a Statisticiansome instruction on the best way to share data to avoid the most common pitfalls and sources of delay in the transition from data collection to data analysis.
  3. Bazela build tool, i.e. a tool that will run compilers and tests to assemble your software, similar to Make, Ant, Gradle, Buck, Pants, and Maven. Google’s build tool, to be precise.
  4. You Can’t Have Exactly-Once Delivery — not about the worst post office ever. FLP and the Two Generals Problem are not design complexities, they are impossibility results.
Comment
Four short links: 12 March 2015

Four short links: 12 March 2015

Billion Node Graphs, Asynchronous Systems, Deep Learning Hardware, and Vision Resources

  1. Mining Billion Node Graphs: Patterns and Scalable Algorithms (PDF) — slides from a CMU academic’s talk at C-BIG 2012.
  2. There Is No NowOne of the most important results in the theory of distributed systems is an impossibility result, showing one of the limits of the ability to build systems that work in a world where things can fail. This is generally referred to as the FLP result, named for its authors, Fischer, Lynch, and Paterson. Their work, which won the 2001 Dijkstra Prize for the most influential paper in distributed computing, showed conclusively that some computational problems that are achievable in a “synchronous” model in which hosts have identical or shared clocks are impossible under a weaker, asynchronous system model.
  3. Deep Learning Hardware GuideOne of the worst things you can do when building a deep learning system is to waste money on hardware that is unnecessary. Here I will guide you step by step through the hardware you will need for a cheap high performance system.
  4. Awesome Computer Vision — curated list of computer vision resources.
Comment
Four short links: 13 February 2015

Four short links: 13 February 2015

Web Post-Mortem, Data Flow, Hospital Robots, and Robust Complex Networks

  1. What Happened to Web Intents (Paul Kinlan) — I love post-mortems, and this is a thoughtful one.
  2. Apache NiFi — incubated open source project for data flow.
  3. Tug Hospital Robot (Wired) — It may have an adult voice, but Tug has a childlike air, even though in this hospital you’re supposed to treat it like a wheelchair-bound old lady. It’s just so innocent, so earnest, and at times, a bit helpless. If there’s enough stuff blocking its way in a corridor, for instance, it can’t reroute around the obstruction. This happened to the Tug we were trailing in pediatrics. “Oh, something’s in its way!” a woman in scrubs says with an expression like she herself had ruined the robot’s day. She tries moving the wheeled contraption but it won’t budge. “Uh, oh!” She shoves on it some more and finally gets it to move. “Go, Tug, go!” she exclaims as the robot, true to its programming, continues down the hall.
  4. Improving the Robustness of Complex Networks with Preserving Community Structure (PLoSone) — To improve robustness while minimizing the above three costly changes, we first seek to verify that the community structure of networks actually do identify the robustness and vulnerability of networks to some extent. Then, we propose an effective 3-step strategy for robustness improvement, which retains the degree distribution of a network, as well as preserves its community structure.
Comment
Four short links: 31 December 2014

Four short links: 31 December 2014

Feudal Employment, Untrusted Computing, Nerd Entitlement, and Paxos Explained

  1. Governance for the New Class of Worker (Matt Webb) — there is a new class of worker. They’re not inside the company – not benefiting from job security or healthcare – but their livelihoods in large part dependent on it, the transaction cost of moving to a competitor deliberately kept high. Or the worker is, without seeing any of the upside of success, taking on the risk or bearing the cost of the company’s expansion and operation.
  2. Hidden Code in Your Chipset (Slideshare) — there’s a processor that supervises your processor, and it’s astonishingly fully-featured (to the point of having privileged access to the network and being able to run Java code).
  3. On Nerd EntitlementPrivilege doesn’t mean you don’t suffer. The best part of 2014 was the tech/net feminist consciousness-raising/uprising. That’s probably the wrong label for it, but bullshit is being called that was ignored years ago. I think we’ve collectively found the next thing we fix that future generations will look back on us and wonder why it went unremarked-upon for so long.
  4. Understanding Paxos — a simple introduction, with animations, to one of the key algorithms in distributed systems.
Comment