[iskander]

>Academia is already facing difficulties in computer science because much of the state-of-the-art research is being done by private companies...As a consequence, there are a number of areas in computer science where the leading academic papers are literally a good half decade behind the state-of-the-art that is buried in NDAs.

Can you elaborate on which areas of CS academia you think are more sophisticated in the corporate wilds? Other than systems work at Google, I haven't encountered any subtopics which aren't dominated by ideas from traditional research centers (either university labs or academic research units at MSR, IBM, etc...)

[wtallis]

One area that's heavily under NDA (though perhaps not quite the situation described) is graphics drivers. NVidia and AMD both have high-performance graphics drivers, but the open-source alternatives (reverse-engineered for NVidia, but AMD sponsors their open-source Linux driver) are far behind. They're reluctant to even share hardware specs, let alone the code from their proprietary drivers.

Part of the reluctance is that they don't want to compromise the DRM systems that their products are complicit in, but most of it is patent related. They already have to pay royalties to many graphics has-beens for things like S3TC, and the fear is that if the details of what their hardware and software is doing were publicly available, they'd be painting targets all over themselves. The people AMD employs to help with their open-source Linux drivers are constantly citing "legal review" as the hold-up for releasing new specs or code, but never that they're concerned about making it easier for NVidia to reverse-engineer their stuff.

[fghh45sdfhr3]

One area that's heavily under NDA (though perhaps not quite the situation described) is graphics drivers.

But that's not because the algorithms are new and awesome, it's mostly just because the exact specs of the hardware are not happily shared.

CS research is not about lack of hardware specs.

It is also not about protecting someones DRM.

It is also not about crappy patents.

And it is also not about how easy your published work is to reverse-engineer.

None of those are CS research problems.

[wtallis]

> "But that's not because the algorithms are new and awesome, it's mostly just because the exact specs of the hardware are not happily shared."

No, that doesn't fully explain the situation. They're worried about far more than their competitor knowing how many ALUs are on their GPU. Graphics drivers have to solve several hard problems: optimizations for shader compilers, scheduling, and memory management, and that's before you even get into the graphics-specific stuff. In recent years, GPUs have been one of the most active areas of research into computer architectures. For you to suggest that a modern GPU and its drivers don's embody any hardcore CS research is just plain stupid - if GPUs were simple to build, then Intel would have shipped a good IGP by now.

[fghh45sdfhr3]

I not disagreeing that they do include core CS problems, I just don't believe their solutions to the core of those problems are that far ahead of academia.

In terms of the vendor specific features, sure, neither academia, not anyone else knows much about them. But in the fundamentals of scheduling, binning, etc, I don't think anyone is very far ahead of all of academia.

[wtallis]

Just because a grad student somewhere has discovered an algorithm doesn't mean their knowledge is on par with the company that knows when that algorithm is actually useful, and has shipped code using it. Writing a textbook on matrix decompositions and factorizations doesn't mean you would be able to create a Google-quality search engine given a large enough server farm and a few months to crawl the web. The state-of-the-art is far more than what's theoretically possible, and the really abstract stuff like proofs of bounds on the asymptotic running time of a solution to a problem have never been the kind of research that is patentable. Even if the equation is known in academia, if a company spent years and millions of dollars to find the right coefficients, then the company is ahead of academia in a non-trivial way. Reduction to practice matters.

[gbhn]

But that's the opponents' point -- the values of such coefficients make excellent trade secrets, but the fact that you can, for instance, invert a matrix, is poor material for a patent.

Personally, I think the limits of software patents should be to precise algorithms. This ends up protecting the fruits of laborious research which have found optimal solutions (in an engineering sense) to things like cryptography, or graphics, or video compression. The disclosure of these algorithms would indeed advance research and the useful arts, and the disclosure would be advantageous. Most software patents, though, are "a system for clicking on a button, but INNA FONE!!!" type of nonsense where disclosure does absolutely nothing, anyway. So sure, such posers ought to be able to patent the exact algorithm they use to click their button, if they want, but NOT to patent the idea of clicking a button, which is in effect what we have now.

This separation goes pretty far towards the concerns the OP wrote down, and is, I think, pretty intuitive to most programmers. It is also the closest to copyright, but without requiring the legal jangle of "well, you used the variable i, but I used j, so therefore my code is different!!!1!one!!" kind of nonsense that pure copyright might result in. Patenting a precise series of disclosed algorithmic steps is helpful, and is a bright line for the patent office, and easy to adjudicate as well. Patenting the notion that you can transmit particular kinds of data over a network, or have certain programs talk to other programs, is where the PTO went off the rails.

[jandrewrogers]

I consider corporate research centers to be non-academic. I know for a fact they produce a considerable number of CS advances that are not published but which are used internally or quietly embedded into expensive products.

In all three areas where I have been involved in R&D -- distributed spatial indexing, parallel graph analysis, databases -- the state-of-the-art has been under NDA for years. Basically, any company where pushing the envelope on their advanced software systems is a significant competitive advantage.

The most obvious example is parallelizing graph analysis. Benchmarks like Graph500 are dominated by systems operating at a scale far, far beyond the reach of any algorithm in literature. There is ample evidence that vastly superior algorithms exist relative to what CS academia is producing. In fact, when I was active in this particular area almost four years ago, there were (at least) two different algorithms being used to achieve this kind of scale-out.

On the other hand, most people are not familiar with what is in the literature.

[vy8vWJlco]

The premise of the patent system is that people wouldn't naturally document a secret process and so providing an external incentive to do so is a net benefit. This is a superficial presumption at best...

Since research must be peer-reviewed to be debunked or even understood, there is a limit to the benefits of trade-secrets and NDAs as a hedge against competition. You might be able to get a short-term advantage, but it's unsustainable because the knowledge cannot transfer. An employer ties his/her own hands by internalizing process knowledge (ironically, not what was intended): the increasingly small number of people with the specialized knowledge having increasing leverage; the profits are destroyed when your only choice is to pay a small number of in-house experts whatever they want, because noone else can do the job. This doesn't happen overnight mind you, but it would after at most a single generation (the point at which you have to train your successors or close shop).

IMHO, the case for patents is hollow.

> "On the other hand, most people are not familiar with what is in the literature."

This is the larger friction. We will continue to grasp at straws until people have thorough and integrative education and access to existing techniques without exorbitant costs or fear of prosecution. Even major (though more frequently minor) improvements over existing techniques are only temporary wins; research that never becomes widely disseminated and understood ultimately becomes a sunk cost.

To refer to your original 3-points:

1) I totally agree, "computer technology is over-run with frivolous, vague, stupid, conflicting, and contradictory patents."

2) I do not discount the level of investment required to push the boundaries of process knowledge, but I would say that it is part of normal competition and those costs are part fo being in the game. A trade-secret is only valuable for a few years, after which it can and should be disclosed to maintain a low cost of employment (unless you want your employees becoming your partners). My point is that patents don't provide any significant benefit toward this end and it has always been the case that if a company or person doesn't have to reveal it's process, it won't. (And the employment of patent lawyers and trolls is not itself a valuable end.)

3) "Academia is already facing difficulties..." Again, I would say this is a temporary situation at worst. We should not extrapolate from the first few points on this curve. We know more about the context: companies that don't publish (internalize all their knowledge) will eventually have no ground to stand on since no one will be able to contribute without an understanding of their internal processes. At most a company can keep only as much knowledge as they can afford to convey, at their expense, to a new hire. They would have to turn their back on a lot of our publicly standardized and centralized educational framework. Unless something were to fundamentally change, I don't see any way those costs can be justified.

[jackowayed]

Databases. Oracle, Microsoft, etc. have figured out a lot about how to make high-performance query execution engines and transactional storage systems and written about very little of it.

Research has caught up some, but it definitely lags.

[kkowalczyk]

You're confusing solid engineering with research.

SQL Server started as a fork of Sybase (Microsoft bought Sybase's source code and started hacking). Sybase, in turn, was based on Ingress and "Ingres was first created as a research project at the University of California, Berkeley, starting in the early 1970s and ending in the early 1980s" (http://en.wikipedia.org/wiki/Ingres_(database)).

SQL Server is literally based on technology for 70s.

Ingress was started by Michael Stonebraker, who then did PostgreSQL (which added novel, at the time, extensions to relational model), who then did Aurora, C-Store and Vertical (column-oriented databases), them Morpheus, then H-Store and then VoltDB.

Stonebreaker did more research (as in: creating novel things) than Microsoft as a whole in SQL Server.

SQL Server is a great database but it's a result of Microsoft paying an army of programmers for 24 years to work on improving a single product. It's a result of running a profiler often, not some unknown-to-the-world algorithms.

[justincormack]

That has happened in the past too, in many areas. eg compiler research used to be like this. But many of the companies died, and stuff was reinvented again, probably wastefully (or differently, who knows).

[fghh45sdfhr3]

I am sure they have a lot of tiny performance improvements. But since when is CS research about tiny performance improvements?

It's not like Oracle or anyone else has any secret algorithm which runs in linear time when all of academia only knows of exponential time solutions for the same class of problems.

[calpaterson]

If "CS research" includes "Software Engineering" then yes, query plan optimisers are definitely currently researched.

[wtallis]

Do you think quicksort was an unimportant advance? After all, it's only O(n log n) in the average case, and is O(n^2) in the worst case. By your standards, it shouldn't have been seen as any kind of improvement over mergesort.

[stcredzero]

> there are a number of areas in computer science where the leading academic papers are literally a good half decade behind the state-of-the-art that is buried in NDAs.

At a former company, I learned of the existence of a code packaging technology that would apply arbitrary code changes to a running VM instance atomically. By 2002, it was possible to implement a web application server whose pages were JIT compiled to machine code yet still upload and apply a code change atomically. With some care, transactions in flight could even be stopped mid-way and continue execution on the new code base. On top of that, it was possible to debug page renderings and change and recompile code in the debugger. Not so fancy now, but this was pretty slick in 2002.

[pcl]

From what I understand, a lot of the FPGA and vector calculus stuff that financial-services companies are doing is leaps and bounds ahead of the published materials. But I'm not under NDA in any related projects, so that's just hearsay.

[fghh45sdfhr3]

I'm pretty sure we have Wall street quants here, unless one of them offers a convincing argument that yes, they are well ahead of academia, I don't believe it.

In my anecdotal experience, the financial industry is light years behind most post-graduate level mathematicians and physicists. Finanical math is kind of scary for anyone who knows more math than the average banker.

[pcl]

But that's the thing, right? Most of the people working on this stuff are disincented from discussing it, both contractually and in terms of their own profit motives.

[bskap]

That's because you never hear about what's going on outside of the research centers- they're all under NDA.

[Buttons840]

Do companies want to profit from this computer science research being done under a NDA? Don't they have to release these advances in the form of a product to earn a profit?

Then show me some products which demonstrate this "cutting-edge" computer science research.

[wcarss]

They don't necessarily have to, and even if they did, it may not be obvious.

Consider a financial company working to improve prediction algorithms for their in-house use, hiring smartypants PhDs and giving them free reign and great pay. The result after ten years could be way ahead (or even just a little ahead) of the academic world's work and never release a product with a sticker for a big shiny new algorithm.

The firm wouldn't even have to stand out in its success; it could do reasonably well compared to others, and just attribute a lot of its modest success to its algorithmic insights.

Even in externally released products, really clever ways to get around things aren't necessarily visible. Just today I was reading about Jonathan Blow's work [1] on localised kriging [2] for his upcoming game The Witness. He's pulling from advanced geostatics academia for a little feature he wanted in a game, and if he didn't blog about it (and then discuss enhancements in the comments) no one would know it existed - even once the game is released. A small example to be sure, but I think it exemplifies the point.

[1] http://the-witness.net/news/2010/05/kriging-is-cool/ [2] http://en.wikipedia.org/wiki/Kriging

[raquo]

I don't see how this situation is an issue of patents, really. A company that is decidedly keeping its prediction technology secret to gain an edge in a market which is entirely about being better at prediction than the other guys is not going to patent and therefore open source their technology no matter what happens to the patent system.

[geofft]

Patents exist to encourage inventions to be published, in exchange for exclusive licensing rights of the invention. Their entire purpose is to be an alternative to trade secrets. So it is fair to say that effective patents are those that are best at convincing people that they should publish their work instead of keeping it secret, and that there will be no financial impact to them doing so.

[michaelt]

Patents only offer you protection against detectable infringement. If it's possible for company A to keep their algorithm secret, it's possible for company B to keep their infringement secret.

[raquo]

I understand that, but in the examples given in this thread of CS areas that are lacking published research, it is pretty clear that companies develop technologies in secret because secrecy provides them with more value and serves as a better protection against competitors than patents would. You just can't make a financial firm share their trading recipes that have any sort of value. We're lucky they don't patent trading/financial versions of 1-click-to-buy.

[anonymoushn]

A company could instead profit by trading using their results, and some results could belong to governments.

I'm reminded that my graph theory professor said that he could factor polynomials over finite fields in polynomial time, but that he could not tell me how to do it.

[iskander]

...but doesn't this sort of argument reduce to "you can't disprove the existence of unicorns?". Eventually this cutting-edge stuff has to come out from under NDA, so we should at least know of major advances from the 90s which were only revealed later.