**nhaliday : lower-bounds**
42

The Existential Risk of Math Errors - Gwern.net

july 2019 by nhaliday

How big is this upper bound? Mathematicians have often made errors in proofs. But it’s rarer for ideas to be accepted for a long time and then rejected. But we can divide errors into 2 basic cases corresponding to type I and type II errors:

1. Mistakes where the theorem is still true, but the proof was incorrect (type I)

2. Mistakes where the theorem was false, and the proof was also necessarily incorrect (type II)

Before someone comes up with a final answer, a mathematician may have many levels of intuition in formulating & working on the problem, but we’ll consider the final end-product where the mathematician feels satisfied that he has solved it. Case 1 is perhaps the most common case, with innumerable examples; this is sometimes due to mistakes in the proof that anyone would accept is a mistake, but many of these cases are due to changing standards of proof. For example, when David Hilbert discovered errors in Euclid’s proofs which no one noticed before, the theorems were still true, and the gaps more due to Hilbert being a modern mathematician thinking in terms of formal systems (which of course Euclid did not think in). (David Hilbert himself turns out to be a useful example of the other kind of error: his famous list of 23 problems was accompanied by definite opinions on the outcome of each problem and sometimes timings, several of which were wrong or questionable5.) Similarly, early calculus used ‘infinitesimals’ which were sometimes treated as being 0 and sometimes treated as an indefinitely small non-zero number; this was incoherent and strictly speaking, practically all of the calculus results were wrong because they relied on an incoherent concept - but of course the results were some of the greatest mathematical work ever conducted6 and when later mathematicians put calculus on a more rigorous footing, they immediately re-derived those results (sometimes with important qualifications), and doubtless as modern math evolves other fields have sometimes needed to go back and clean up the foundations and will in the future.7

...

Isaac Newton, incidentally, gave two proofs of the same solution to a problem in probability, one via enumeration and the other more abstract; the enumeration was correct, but the other proof totally wrong and this was not noticed for a long time, leading Stigler to remark:

...

TYPE I > TYPE II?

“Lefschetz was a purely intuitive mathematician. It was said of him that he had never given a completely correct proof, but had never made a wrong guess either.”

- Gian-Carlo Rota13

Case 2 is disturbing, since it is a case in which we wind up with false beliefs and also false beliefs about our beliefs (we no longer know that we don’t know). Case 2 could lead to extinction.

...

Except, errors do not seem to be evenly & randomly distributed between case 1 and case 2. There seem to be far more case 1s than case 2s, as already mentioned in the early calculus example: far more than 50% of the early calculus results were correct when checked more rigorously. Richard Hamming attributes to Ralph Boas a comment that while editing Mathematical Reviews that “of the new results in the papers reviewed most are true but the corresponding proofs are perhaps half the time plain wrong”.

...

Gian-Carlo Rota gives us an example with Hilbert:

...

Olga labored for three years; it turned out that all mistakes could be corrected without any major changes in the statement of the theorems. There was one exception, a paper Hilbert wrote in his old age, which could not be fixed; it was a purported proof of the continuum hypothesis, you will find it in a volume of the Mathematische Annalen of the early thirties.

...

Leslie Lamport advocates for machine-checked proofs and a more rigorous style of proofs similar to natural deduction, noting a mathematician acquaintance guesses at a broad error rate of 1/329 and that he routinely found mistakes in his own proofs and, worse, believed false conjectures30.

[more on these "structured proofs":

https://academia.stackexchange.com/questions/52435/does-anyone-actually-publish-structured-proofs

https://mathoverflow.net/questions/35727/community-experiences-writing-lamports-structured-proofs

]

We can probably add software to that list: early software engineering work found that, dismayingly, bug rates seem to be simply a function of lines of code, and one would expect diseconomies of scale. So one would expect that in going from the ~4,000 lines of code of the Microsoft DOS operating system kernel to the ~50,000,000 lines of code in Windows Server 2003 (with full systems of applications and libraries being even larger: the comprehensive Debian repository in 2007 contained ~323,551,126 lines of code) that the number of active bugs at any time would be… fairly large. Mathematical software is hopefully better, but practitioners still run into issues (eg Durán et al 2014, Fonseca et al 2017) and I don’t know of any research pinning down how buggy key mathematical systems like Mathematica are or how much published mathematics may be erroneous due to bugs. This general problem led to predictions of doom and spurred much research into automated proof-checking, static analysis, and functional languages31.

[related:

https://mathoverflow.net/questions/11517/computer-algebra-errors

I don't know any interesting bugs in symbolic algebra packages but I know a true, enlightening and entertaining story about something that looked like a bug but wasn't.

Define sinc𝑥=(sin𝑥)/𝑥.

Someone found the following result in an algebra package: ∫∞0𝑑𝑥sinc𝑥=𝜋/2

They then found the following results:

...

So of course when they got:

∫∞0𝑑𝑥sinc𝑥sinc(𝑥/3)sinc(𝑥/5)⋯sinc(𝑥/15)=(467807924713440738696537864469/935615849440640907310521750000)𝜋

hmm:

Which means that nobody knows Fourier analysis nowdays. Very sad and discouraging story... – fedja Jan 29 '10 at 18:47

--

Because the most popular systems are all commercial, they tend to guard their bug database rather closely -- making them public would seriously cut their sales. For example, for the open source project Sage (which is quite young), you can get a list of all the known bugs from this page. 1582 known issues on Feb.16th 2010 (which includes feature requests, problems with documentation, etc).

That is an order of magnitude less than the commercial systems. And it's not because it is better, it is because it is younger and smaller. It might be better, but until SAGE does a lot of analysis (about 40% of CAS bugs are there) and a fancy user interface (another 40%), it is too hard to compare.

I once ran a graduate course whose core topic was studying the fundamental disconnect between the algebraic nature of CAS and the analytic nature of the what it is mostly used for. There are issues of logic -- CASes work more or less in an intensional logic, while most of analysis is stated in a purely extensional fashion. There is no well-defined 'denotational semantics' for expressions-as-functions, which strongly contributes to the deeper bugs in CASes.]

...

Should such widely-believed conjectures as P≠NP or the Riemann hypothesis turn out be false, then because they are assumed by so many existing proofs, a far larger math holocaust would ensue38 - and our previous estimates of error rates will turn out to have been substantial underestimates. But it may be a cloud with a silver lining, if it doesn’t come at a time of danger.

https://mathoverflow.net/questions/338607/why-doesnt-mathematics-collapse-down-even-though-humans-quite-often-make-mista

more on formal methods in programming:

https://www.quantamagazine.org/formal-verification-creates-hacker-proof-code-20160920/

https://intelligence.org/2014/03/02/bob-constable/

https://softwareengineering.stackexchange.com/questions/375342/what-are-the-barriers-that-prevent-widespread-adoption-of-formal-methods

Update: measured effort

In the October 2018 issue of Communications of the ACM there is an interesting article about Formally verified software in the real world with some estimates of the effort.

Interestingly (based on OS development for military equipment), it seems that producing formally proved software requires 3.3 times more effort than with traditional engineering techniques. So it's really costly.

On the other hand, it requires 2.3 times less effort to get high security software this way than with traditionally engineered software if you add the effort to make such software certified at a high security level (EAL 7). So if you have high reliability or security requirements there is definitively a business case for going formal.

WHY DON'T PEOPLE USE FORMAL METHODS?: https://www.hillelwayne.com/post/why-dont-people-use-formal-methods/

You can see examples of how all of these look at Let’s Prove Leftpad. HOL4 and Isabelle are good examples of “independent theorem” specs, SPARK and Dafny have “embedded assertion” specs, and Coq and Agda have “dependent type” specs.6

If you squint a bit it looks like these three forms of code spec map to the three main domains of automated correctness checking: tests, contracts, and types. This is not a coincidence. Correctness is a spectrum, and formal verification is one extreme of that spectrum. As we reduce the rigour (and effort) of our verification we get simpler and narrower checks, whether that means limiting the explored state space, using weaker types, or pushing verification to the runtime. Any means of total specification then becomes a means of partial specification, and vice versa: many consider Cleanroom a formal verification technique, which primarily works by pushing code review far beyond what’s humanly possible.

...

The question, then: “is 90/95/99% correct significantly cheaper than 100% correct?” The answer is very yes. We all are comfortable saying that a codebase we’ve well-tested and well-typed is mostly correct modulo a few fixes in prod, and we’re even writing more than four lines of code a day. In fact, the vast… [more]

ratty
gwern
analysis
essay
realness
truth
correctness
reason
philosophy
math
proofs
formal-methods
cs
programming
engineering
worse-is-better/the-right-thing
intuition
giants
old-anglo
error
street-fighting
heuristic
zooming
risk
threat-modeling
software
lens
logic
inference
physics
differential
geometry
estimate
distribution
robust
speculation
nonlinearity
cost-benefit
convexity-curvature
measure
scale
trivia
cocktail
history
early-modern
europe
math.CA
rigor
news
org:mag
org:sci
miri-cfar
pdf
thesis
comparison
examples
org:junk
q-n-a
stackex
pragmatic
tradeoffs
cracker-prog
techtariat
invariance
DSL
chart
ecosystem
grokkability
heavyweights
CAS
static-dynamic
lower-bounds
complexity
tcs
open-problems
big-surf
ideas
certificates-recognition
proof-systems
PCP
mediterranean
SDP
meta:prediction
epistemic
questions
guessing
distributed
overflow
nibble
soft-question
track-record
big-list
hmm
frontier
state-of-art
move-fast-(and-break-things)
grokkability-clarity
technical-writing
trust
1. Mistakes where the theorem is still true, but the proof was incorrect (type I)

2. Mistakes where the theorem was false, and the proof was also necessarily incorrect (type II)

Before someone comes up with a final answer, a mathematician may have many levels of intuition in formulating & working on the problem, but we’ll consider the final end-product where the mathematician feels satisfied that he has solved it. Case 1 is perhaps the most common case, with innumerable examples; this is sometimes due to mistakes in the proof that anyone would accept is a mistake, but many of these cases are due to changing standards of proof. For example, when David Hilbert discovered errors in Euclid’s proofs which no one noticed before, the theorems were still true, and the gaps more due to Hilbert being a modern mathematician thinking in terms of formal systems (which of course Euclid did not think in). (David Hilbert himself turns out to be a useful example of the other kind of error: his famous list of 23 problems was accompanied by definite opinions on the outcome of each problem and sometimes timings, several of which were wrong or questionable5.) Similarly, early calculus used ‘infinitesimals’ which were sometimes treated as being 0 and sometimes treated as an indefinitely small non-zero number; this was incoherent and strictly speaking, practically all of the calculus results were wrong because they relied on an incoherent concept - but of course the results were some of the greatest mathematical work ever conducted6 and when later mathematicians put calculus on a more rigorous footing, they immediately re-derived those results (sometimes with important qualifications), and doubtless as modern math evolves other fields have sometimes needed to go back and clean up the foundations and will in the future.7

...

Isaac Newton, incidentally, gave two proofs of the same solution to a problem in probability, one via enumeration and the other more abstract; the enumeration was correct, but the other proof totally wrong and this was not noticed for a long time, leading Stigler to remark:

...

TYPE I > TYPE II?

“Lefschetz was a purely intuitive mathematician. It was said of him that he had never given a completely correct proof, but had never made a wrong guess either.”

- Gian-Carlo Rota13

Case 2 is disturbing, since it is a case in which we wind up with false beliefs and also false beliefs about our beliefs (we no longer know that we don’t know). Case 2 could lead to extinction.

...

Except, errors do not seem to be evenly & randomly distributed between case 1 and case 2. There seem to be far more case 1s than case 2s, as already mentioned in the early calculus example: far more than 50% of the early calculus results were correct when checked more rigorously. Richard Hamming attributes to Ralph Boas a comment that while editing Mathematical Reviews that “of the new results in the papers reviewed most are true but the corresponding proofs are perhaps half the time plain wrong”.

...

Gian-Carlo Rota gives us an example with Hilbert:

...

Olga labored for three years; it turned out that all mistakes could be corrected without any major changes in the statement of the theorems. There was one exception, a paper Hilbert wrote in his old age, which could not be fixed; it was a purported proof of the continuum hypothesis, you will find it in a volume of the Mathematische Annalen of the early thirties.

...

Leslie Lamport advocates for machine-checked proofs and a more rigorous style of proofs similar to natural deduction, noting a mathematician acquaintance guesses at a broad error rate of 1/329 and that he routinely found mistakes in his own proofs and, worse, believed false conjectures30.

[more on these "structured proofs":

https://academia.stackexchange.com/questions/52435/does-anyone-actually-publish-structured-proofs

https://mathoverflow.net/questions/35727/community-experiences-writing-lamports-structured-proofs

]

We can probably add software to that list: early software engineering work found that, dismayingly, bug rates seem to be simply a function of lines of code, and one would expect diseconomies of scale. So one would expect that in going from the ~4,000 lines of code of the Microsoft DOS operating system kernel to the ~50,000,000 lines of code in Windows Server 2003 (with full systems of applications and libraries being even larger: the comprehensive Debian repository in 2007 contained ~323,551,126 lines of code) that the number of active bugs at any time would be… fairly large. Mathematical software is hopefully better, but practitioners still run into issues (eg Durán et al 2014, Fonseca et al 2017) and I don’t know of any research pinning down how buggy key mathematical systems like Mathematica are or how much published mathematics may be erroneous due to bugs. This general problem led to predictions of doom and spurred much research into automated proof-checking, static analysis, and functional languages31.

[related:

https://mathoverflow.net/questions/11517/computer-algebra-errors

I don't know any interesting bugs in symbolic algebra packages but I know a true, enlightening and entertaining story about something that looked like a bug but wasn't.

Define sinc𝑥=(sin𝑥)/𝑥.

Someone found the following result in an algebra package: ∫∞0𝑑𝑥sinc𝑥=𝜋/2

They then found the following results:

...

So of course when they got:

∫∞0𝑑𝑥sinc𝑥sinc(𝑥/3)sinc(𝑥/5)⋯sinc(𝑥/15)=(467807924713440738696537864469/935615849440640907310521750000)𝜋

hmm:

Which means that nobody knows Fourier analysis nowdays. Very sad and discouraging story... – fedja Jan 29 '10 at 18:47

--

Because the most popular systems are all commercial, they tend to guard their bug database rather closely -- making them public would seriously cut their sales. For example, for the open source project Sage (which is quite young), you can get a list of all the known bugs from this page. 1582 known issues on Feb.16th 2010 (which includes feature requests, problems with documentation, etc).

That is an order of magnitude less than the commercial systems. And it's not because it is better, it is because it is younger and smaller. It might be better, but until SAGE does a lot of analysis (about 40% of CAS bugs are there) and a fancy user interface (another 40%), it is too hard to compare.

I once ran a graduate course whose core topic was studying the fundamental disconnect between the algebraic nature of CAS and the analytic nature of the what it is mostly used for. There are issues of logic -- CASes work more or less in an intensional logic, while most of analysis is stated in a purely extensional fashion. There is no well-defined 'denotational semantics' for expressions-as-functions, which strongly contributes to the deeper bugs in CASes.]

...

Should such widely-believed conjectures as P≠NP or the Riemann hypothesis turn out be false, then because they are assumed by so many existing proofs, a far larger math holocaust would ensue38 - and our previous estimates of error rates will turn out to have been substantial underestimates. But it may be a cloud with a silver lining, if it doesn’t come at a time of danger.

https://mathoverflow.net/questions/338607/why-doesnt-mathematics-collapse-down-even-though-humans-quite-often-make-mista

more on formal methods in programming:

https://www.quantamagazine.org/formal-verification-creates-hacker-proof-code-20160920/

https://intelligence.org/2014/03/02/bob-constable/

https://softwareengineering.stackexchange.com/questions/375342/what-are-the-barriers-that-prevent-widespread-adoption-of-formal-methods

Update: measured effort

In the October 2018 issue of Communications of the ACM there is an interesting article about Formally verified software in the real world with some estimates of the effort.

Interestingly (based on OS development for military equipment), it seems that producing formally proved software requires 3.3 times more effort than with traditional engineering techniques. So it's really costly.

On the other hand, it requires 2.3 times less effort to get high security software this way than with traditionally engineered software if you add the effort to make such software certified at a high security level (EAL 7). So if you have high reliability or security requirements there is definitively a business case for going formal.

WHY DON'T PEOPLE USE FORMAL METHODS?: https://www.hillelwayne.com/post/why-dont-people-use-formal-methods/

You can see examples of how all of these look at Let’s Prove Leftpad. HOL4 and Isabelle are good examples of “independent theorem” specs, SPARK and Dafny have “embedded assertion” specs, and Coq and Agda have “dependent type” specs.6

If you squint a bit it looks like these three forms of code spec map to the three main domains of automated correctness checking: tests, contracts, and types. This is not a coincidence. Correctness is a spectrum, and formal verification is one extreme of that spectrum. As we reduce the rigour (and effort) of our verification we get simpler and narrower checks, whether that means limiting the explored state space, using weaker types, or pushing verification to the runtime. Any means of total specification then becomes a means of partial specification, and vice versa: many consider Cleanroom a formal verification technique, which primarily works by pushing code review far beyond what’s humanly possible.

...

The question, then: “is 90/95/99% correct significantly cheaper than 100% correct?” The answer is very yes. We all are comfortable saying that a codebase we’ve well-tested and well-typed is mostly correct modulo a few fixes in prod, and we’re even writing more than four lines of code a day. In fact, the vast… [more]

july 2019 by nhaliday

Applications of computational learning theory in the cognitive sciences - Psychology & Neuroscience Stack Exchange

february 2019 by nhaliday

1. Gold's theorem on the unlearnability in the limit of certain sets of languages, among them context-free ones.

2. Ronald de Wolf's master's thesis on the impossibility to PAC-learn context-free languages.

The first made quiet a stir in the poverty-of-the-stimulus debate, and the second has been unnoticed by cognitive science.

q-n-a
stackex
psychology
cog-psych
learning
learning-theory
machine-learning
PAC
lower-bounds
no-go
language
linguistics
models
fall-2015
2. Ronald de Wolf's master's thesis on the impossibility to PAC-learn context-free languages.

The first made quiet a stir in the poverty-of-the-stimulus debate, and the second has been unnoticed by cognitive science.

february 2019 by nhaliday

Computer Scientists Close In on Unique Games Conjecture Proof | Quanta Magazine

news org:mag org:sci popsci tcs cs computation UGC complexity approximation lower-bounds hardness nibble org:inst rand-approx proofs big-surf announcement SDP optimization open-problems questions research

june 2018 by nhaliday

news org:mag org:sci popsci tcs cs computation UGC complexity approximation lower-bounds hardness nibble org:inst rand-approx proofs big-surf announcement SDP optimization open-problems questions research

june 2018 by nhaliday

The Physics of Information Processing Superobjects: Daily Life Among the Jupiter Brains

nibble pdf study article essay ratty bostrom physics lower-bounds interdisciplinary computation frontier singularity civilization communication time phys-energy thermo entropy-like lens intelligence futurism philosophy software hardware enhancement no-go data scale magnitude network-structure structure complex-systems concurrency density bits retention mechanics electromag quantum quantum-info speed information-theory measure chemistry gravity relativity the-world-is-just-atoms dirty-hands skunkworks gedanken ideas hard-tech nitty-gritty intricacy len:long spatial whole-partial-many frequency neuro internet web trivia cocktail humanity composition-decomposition instinct reason illusion the-self psychology cog-psych dennett within-without signal-noise coding-theory quotes scifi-fantasy fiction giants death long-short-run janus eden-heaven efficiency finiteness iteration-recursion cycles nietzschean big-peeps examples

april 2018 by nhaliday

nibble pdf study article essay ratty bostrom physics lower-bounds interdisciplinary computation frontier singularity civilization communication time phys-energy thermo entropy-like lens intelligence futurism philosophy software hardware enhancement no-go data scale magnitude network-structure structure complex-systems concurrency density bits retention mechanics electromag quantum quantum-info speed information-theory measure chemistry gravity relativity the-world-is-just-atoms dirty-hands skunkworks gedanken ideas hard-tech nitty-gritty intricacy len:long spatial whole-partial-many frequency neuro internet web trivia cocktail humanity composition-decomposition instinct reason illusion the-self psychology cog-psych dennett within-without signal-noise coding-theory quotes scifi-fantasy fiction giants death long-short-run janus eden-heaven efficiency finiteness iteration-recursion cycles nietzschean big-peeps examples

april 2018 by nhaliday

Complexity no Bar to AI - Gwern.net

april 2018 by nhaliday

Critics of AI risk suggest diminishing returns to computing (formalized asymptotically) means AI will be weak; this argument relies on a large number of questionable premises and ignoring additional resources, constant factors, and nonlinear returns to small intelligence advantages, and is highly unlikely. (computer science, transhumanism, AI, R)

created: 1 June 2014; modified: 01 Feb 2018; status: finished; confidence: likely; importance: 10

ratty
gwern
analysis
faq
ai
risk
speedometer
intelligence
futurism
cs
computation
complexity
tcs
linear-algebra
nonlinearity
convexity-curvature
average-case
adversarial
article
time-complexity
singularity
iteration-recursion
magnitude
multiplicative
lower-bounds
no-go
performance
hardware
humanity
psychology
cog-psych
psychometrics
iq
distribution
moments
complement-substitute
hanson
ems
enhancement
parable
detail-architecture
universalism-particularism
neuro
ai-control
environment
climate-change
threat-modeling
security
theory-practice
hacker
academia
realness
crypto
rigorous-crypto
usa
government
created: 1 June 2014; modified: 01 Feb 2018; status: finished; confidence: likely; importance: 10

april 2018 by nhaliday

[1711.11561] Measuring the tendency of CNNs to Learn Surface Statistical Regularities

january 2018 by nhaliday

so a significant fraction of CNN classification performance is basically taking a histogram of wavelet coefficients

preprint
org:mat
papers
machine-learning
deep-learning
generalization
speedometer
hmm
:/
computer-vision
structure
fourier
abstraction
composition-decomposition
error
explanans
nibble
model-class
lower-bounds
features
waves
adversarial
counterexample
robust
perturbation
acm
state-of-art
classification
frequency
january 2018 by nhaliday

Correlated Equilibria in Game Theory | Azimuth

july 2017 by nhaliday

Given this, it’s not surprising that Nash equilibria can be hard to find. Last September a paper came out making this precise, in a strong way:

• Yakov Babichenko and Aviad Rubinstein, Communication complexity of approximate Nash equilibria.

The authors show there’s no guaranteed method for players to find even an approximate Nash equilibrium unless they tell each other almost everything about their preferences. This makes finding the Nash equilibrium prohibitively difficult to find when there are lots of players… in general. There are particular games where it’s not difficult, and that makes these games important: for example, if you’re trying to run a government well. (A laughable notion these days, but still one can hope.)

Klarreich’s article in Quanta gives a nice readable account of this work and also a more practical alternative to the concept of Nash equilibrium. It’s called a ‘correlated equilibrium’, and it was invented by the mathematician Robert Aumann in 1974. You can see an attempt to define it here:

baez
org:bleg
nibble
mathtariat
commentary
summary
news
org:mag
org:sci
popsci
equilibrium
GT-101
game-theory
acm
conceptual-vocab
concept
definition
thinking
signaling
coordination
tcs
complexity
communication-complexity
lower-bounds
no-go
liner-notes
big-surf
papers
research
algorithmic-econ
volo-avolo
• Yakov Babichenko and Aviad Rubinstein, Communication complexity of approximate Nash equilibria.

The authors show there’s no guaranteed method for players to find even an approximate Nash equilibrium unless they tell each other almost everything about their preferences. This makes finding the Nash equilibrium prohibitively difficult to find when there are lots of players… in general. There are particular games where it’s not difficult, and that makes these games important: for example, if you’re trying to run a government well. (A laughable notion these days, but still one can hope.)

Klarreich’s article in Quanta gives a nice readable account of this work and also a more practical alternative to the concept of Nash equilibrium. It’s called a ‘correlated equilibrium’, and it was invented by the mathematician Robert Aumann in 1974. You can see an attempt to define it here:

july 2017 by nhaliday

Predicting the outcomes of organic reactions via machine learning: are current descriptors sufficient? | Scientific Reports

july 2017 by nhaliday

As machine learning/artificial intelligence algorithms are defeating chess masters and, most recently, GO champions, there is interest – and hope – that they will prove equally useful in assisting chemists in predicting outcomes of organic reactions. This paper demonstrates, however, that the applicability of machine learning to the problems of chemical reactivity over diverse types of chemistries remains limited – in particular, with the currently available chemical descriptors, fundamental mathematical theorems impose upper bounds on the accuracy with which raction yields and times can be predicted. Improving the performance of machine-learning methods calls for the development of fundamentally new chemical descriptors.

study
org:nat
papers
machine-learning
chemistry
measurement
volo-avolo
lower-bounds
analysis
realness
speedometer
nibble
🔬
applications
frontier
state-of-art
no-go
accuracy
interdisciplinary
july 2017 by nhaliday

Energy of Seawater Desalination

february 2017 by nhaliday

0.66 kcal / liter is the minimum energy required to desalination of one liter of seawater, regardless of the technology applied to the process.

infrastructure
explanation
physics
thermo
objektbuch
data
lower-bounds
chemistry
the-world-is-just-atoms
geoengineering
phys-energy
nibble
oceans
h2o
applications
estimate
🔬
energy-resources
biophysical-econ
stylized-facts
ideas
fluid
volo-avolo
february 2017 by nhaliday

cc.complexity theory - Evidence that PPAD is hard? - Theoretical Computer Science Stack Exchange

q-n-a overflow tcs complexity algorithmic-econ game-theory motivation open-problems lower-bounds research relativization crypto rigorous-crypto nibble big-surf hardness questions equilibrium evidence

february 2017 by nhaliday

q-n-a overflow tcs complexity algorithmic-econ game-theory motivation open-problems lower-bounds research relativization crypto rigorous-crypto nibble big-surf hardness questions equilibrium evidence

february 2017 by nhaliday

Advanced Complexity Theory, Fall 2012

course mit tcs complexity lower-bounds circuits relativization hierarchy communication-complexity boaz-barak random pseudorandomness rand-complexity madhu-sudan pcp approximation 👳 yoga dana-moshkovitz rand-approx naturality counting space-complexity expanders unit

february 2017 by nhaliday

course mit tcs complexity lower-bounds circuits relativization hierarchy communication-complexity boaz-barak random pseudorandomness rand-complexity madhu-sudan pcp approximation 👳 yoga dana-moshkovitz rand-approx naturality counting space-complexity expanders unit

february 2017 by nhaliday

cc.complexity theory - Advanced techniques for determining complexity lower bounds - Theoretical Computer Science Stack Exchange

q-n-a overflow tcs complexity lower-bounds yoga list big-list frontier synthesis circuits algebraic-complexity math.RT research nibble hardness tricki p:whenever knowledge elegance

january 2017 by nhaliday

q-n-a overflow tcs complexity lower-bounds yoga list big-list frontier synthesis circuits algebraic-complexity math.RT research nibble hardness tricki p:whenever knowledge elegance

january 2017 by nhaliday

Computational Complexity: Favorite Theorems: The Yao Principle

january 2017 by nhaliday

The Yao Principle applies when we don't consider the algorithmic complexity of the players. For example in communication complexity we have two players who each have a separate half of an input string and they want to compute some function of the input with the minimum amount of communication between them. The Yao principle states that the best probabilistic strategies for the players will achieve exactly the communication bounds as the best deterministic strategy over a worst-case distribution of inputs.

The Yao Principle plays a smaller role where we measure the running time of an algorithm since applying the Principle would require solving an extremely large linear program. But since so many of our bounds are in information-based models like communication and decision-tree complexity, the Yao Principle, though not particularly complicated, plays an important role in lower bounds in a large number of results in our field.

tcstariat
tcs
complexity
adversarial
rand-approx
algorithms
game-theory
yoga
levers
communication-complexity
random
lower-bounds
average-case
nibble
org:bleg
The Yao Principle plays a smaller role where we measure the running time of an algorithm since applying the Principle would require solving an extremely large linear program. But since so many of our bounds are in information-based models like communication and decision-tree complexity, the Yao Principle, though not particularly complicated, plays an important role in lower bounds in a large number of results in our field.

january 2017 by nhaliday

Adaptive data analysis

acmtariat acm machine-learning stats research research-program exposition science methodology mrtz meta:science differential-privacy liner-notes hypothesis-testing org:bleg nibble metameta 🔬 info-dynamics generalization iteration-recursion data-science online-learning bayesian gelman scitariat frequentist human-ml robust perturbation sensitivity learning-theory information-theory bits lower-bounds no-go volo-avolo adversarial gradient-descent bonferroni

december 2016 by nhaliday

acmtariat acm machine-learning stats research research-program exposition science methodology mrtz meta:science differential-privacy liner-notes hypothesis-testing org:bleg nibble metameta 🔬 info-dynamics generalization iteration-recursion data-science online-learning bayesian gelman scitariat frequentist human-ml robust perturbation sensitivity learning-theory information-theory bits lower-bounds no-go volo-avolo adversarial gradient-descent bonferroni

december 2016 by nhaliday

Harvard CS 229r: Information Theory in Computer Science (Spring 2016)

course harvard information-theory tcs yoga 👳 topics bits madhu-sudan entropy-like motivation communication-complexity lower-bounds mihai algorithms data-structures sublinear space-complexity unit binomial p:* quixotic advanced

october 2016 by nhaliday

course harvard information-theory tcs yoga 👳 topics bits madhu-sudan entropy-like motivation communication-complexity lower-bounds mihai algorithms data-structures sublinear space-complexity unit binomial p:* quixotic advanced

october 2016 by nhaliday

Communication Complexity (for Algorithm Designers) (CS369E), Winter 2015

sublinear course stanford algorithms lower-bounds complexity tcs yoga 👳 lecture-notes topics communication-complexity tim-roughgarden space-complexity sparsity norms data-structures algorithmic-econ game-theory unit compressed-sensing p:someday quixotic advanced

september 2016 by nhaliday

sublinear course stanford algorithms lower-bounds complexity tcs yoga 👳 lecture-notes topics communication-complexity tim-roughgarden space-complexity sparsity norms data-structures algorithmic-econ game-theory unit compressed-sensing p:someday quixotic advanced

september 2016 by nhaliday

Hypercontractivity and its Applications | tcs math

tcs tcstariat washington papers slides survey talks lectures exposition concept estimate math boolean-analysis yoga cool rand-approx optimization algorithms coding-theory math.GR SDP rounding complexity lower-bounds graphs graph-theory UGC org:bleg nibble

may 2016 by nhaliday

tcs tcstariat washington papers slides survey talks lectures exposition concept estimate math boolean-analysis yoga cool rand-approx optimization algorithms coding-theory math.GR SDP rounding complexity lower-bounds graphs graph-theory UGC org:bleg nibble

may 2016 by nhaliday

cc.complexity theory - The importance of Integrality Gap - Theoretical Computer Science Stack Exchange

optimization tcs algorithms lower-bounds research explanation motivation concept q-n-a atoms overflow rounding linear-programming SDP ground-up approximation relaxation nibble discrete

april 2016 by nhaliday

optimization tcs algorithms lower-bounds research explanation motivation concept q-n-a atoms overflow rounding linear-programming SDP ground-up approximation relaxation nibble discrete

april 2016 by nhaliday

Copy this bookmark: