On the cryptographic hardness of finding a Nash equilibrium

I found it annoying that you generally can’t really hear the questions posed by the audience (which includes people like Avi Wigderson), especially considering that there are quite a few of these, especially in the middle section of the lecture. There are intermittent issues with the camera’s focus occasionally throughout the talk, but those are all transitory problems that should not keep you from watching the lecture. The sound issue at the beginning of the talk is resolved after 40 seconds.

One important take-away from this talk, if you choose not to watch it: “to date, there is no known efficient algorithm to find Nash equilibrium in games”. In general this paper – coauthored by the lecturer – seems from a brief skim to cover many of the topics also included in the lecture. I have added some other links to articles and topics covered/mentioned in the lecture below.

Nash’s Existence Theorem.
Reducibility Among Equilibrium Problems (Goldberg & Papadimitriou).
Three-Player Games Are Hard (Daskalakis & Papadimitriou).
3-Nash is PPAD-Complete (Chen & Deng).
PPAD (complexity).
On the (Im)possibility of Obfuscating Programs (Barak et al.).
On the Impossibility of Obfuscation with Auxiliary Input (Goldwasser & Kalai).
On Best-Possible Obfuscation (Goldwasser & Rothblum).
Functional Encryption without Obfuscation (Garg et al.).
On the Complexity of the Parity Argument and Other Inefficient Proofs of Existence (Papadimitriou).
Pseudorandom function family.
Revisiting the Cryptographic Hardness of Finding a Nash Equilibrium (Garg, Pandei & Srinivasan).
Constrained Pseudorandom Functions and Their Applications (Boneh & Waters).
Delegatable Pseudorandom Functions and Applications (Kiayias et al.).
Functional Signatures and Pseudorandom Functions (Boyle, Goldwasser & Ivan).
Universal Constructions and Robust Combiners for Indistinguishability Obfuscation and Witness Encryption (Ananth et al.).


April 18, 2018 Posted by | Computer science, Cryptography, Game theory, Lectures, Mathematics, Papers | Leave a comment

The Internet of Things


Some links to stuff he talks about in the lecture:

The Internet of Things: making the most of the Second Digital Revolution – A report by the UK Government Chief Scientific Adviser.
South–North Water Transfer Project.
FDA approves first smart pill that tracks drug regimen compliance from the inside.
The Internet of Things (IoT)* units installed base by category from 2014 to 2020.
Share of the IoT market by sub-sector worldwide in 2017.
San Diego to Cover Half the City with Intelligent Streetlights.
IPv4 and IPv6 (specifically, he talks a little about the IPv4 address space problem).
General Data Protection Regulation (GDPR).
Shodan (website).
Mirai botnet.
Gait analysis.
Website reveals 73,000 unprotected security cameras with default passwords. (This was just an example link – it’s unclear if the site he used to illustrate his point in that part of the lecture was actually Insecam, but he does talk about the widespread use of default passwords and related security implications during the lecture).
Strava’s fitness heatmaps are a ‘potential catastrophe’.
‘Secure by Design’ (a very recently published proposed UK IoT code of practice).

March 26, 2018 Posted by | Computer science, Engineering, Lectures | Leave a comment

Safety-Critical Systems

Some related links to topics covered in the lecture:

Safety-critical system.
Safety engineering.
Fault tree analysis.
Failure mode and effects analysis.
Value of a statistical life.
ALARP principle.
Hazards and Risk (HSA).
Software system safety.
Aleatoric and epistemic uncertainty.
N-version programming.
An experimental evaluation of the assumption of independence in multiversion programming (Knight & Leveson).
Safety integrity level.
Software for Dependable Systems – Sufficient Evidence? (consensus study report).

March 15, 2018 Posted by | Computer science, Economics, Engineering, Lectures, Statistics | Leave a comment

Sieve methods: what are they, and what are they good for?

Given the nature of the lecture it was difficult to come up with relevant links to include in this post, but these seemed relevant enough to include them here:

Sieve theory.
Inclusion–exclusion principle.
Fundamental lemma of sieve theory.
Parity problem (sieve theory).
Viggo Brun (the lecturer mentions along the way that many of the things he talks about in this lecture are things this guy figured out, but the wiki article is unfortunately very short).

As he notes early on, when working with sieves we’re: “*Interested in objects which are output of some inclusion-exclusion process & *Rather than counting precisely, we want to gain good bounds, but work flexibly.”

‘Counting’ should probably be interpreted loosely here, in the general scheme of things; sieves are mostly used in number theory, but as Maynard mentions presumably similar methods can be used in other mathematical contexts – thus the deliberate use of the word ‘objects’. It seems to be all about trying to ascertain some properties about some objects/sets/whatever, without necessarily imposing much structure (‘are we within the right order of magnitude?’ rather than ‘did we get them all?’). The basic idea behind restricting the amount of structure imposed is, as far as I gathered from the lecture, to make the problem you’re faced with more tractable.

February 24, 2018 Posted by | Lectures, Mathematics | Leave a comment

Some things you need to know about machine learning but didn’t know whom to ask (the grad school version)

Some links to stuff related to the lecture’s coverage:
An overview of gradient descent optimization algorithms.
Rectifier (neural networks) [Relu].
Escaping From Saddle Points – Online Stochastic Gradient for Tensor Decomposition (Ge et al.).
How to Escape Saddle Points Efficiently (closely related to the paper above, presumably one of the ‘recent improvements’ mentioned in the lecture).
Linear classifier.
Concentration inequality.
A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networks (Neyshabur et al.).
Off the convex path (the lecturer’s blog).

February 19, 2018 Posted by | Computer science, Lectures, Mathematics | Leave a comment

Analgesia and Procedural Sedation

I didn’t actually like this lecture all that much, in part because I obviously disagree to some extent with the ideas expressed, but I try to remember to blog lectures I watch these days even if I don’t think they’re all that great. It’s a short lecture, but why not at least add a comment about urine drug screening and monitoring or patient selection/segmentation when you’re talking about patients whom you’re considering discharging with an opioid prescription? Recommending acupuncture in a pain management context? Etc.

Anyway, below a few links to stuff related to the coverage:

Pain Management in the Emergency Department.
WHO analgesic ladder.
Nonsteroidal anti-inflammatory drug.
Fentanyl (“This medication should not be used to treat pain other than chronic cancer pain, especially short-term pain such as migraines or other headaches, pain from an injury, or pain after a medical or dental procedure.” …to put it mildly, that’s not the impression you get from watching this lecture…)
Parenteral opioids in emergency medicine – A systematic review of efficacy and safety.
Procedural Sedation (medscape).

December 22, 2017 Posted by | Lectures, Medicine, Pharmacology | Leave a comment

Concussion and Sequelae of Minor Head Trauma

Some related links:

PECARN Pediatric Head Injury/Trauma Algorithm.
Canadian CT Head Injury/Trauma Rule.
ACEP – Traumatic Brain Injury (Mild – Adult).
AANS – concussion.
Guidelines for the Management of Severe Traumatic Brain Injury – 4th edition.
Return-to-play guidelines.
Second-impact syndrome.
Repetitive Head Injury Syndrome (medscape).
Traumatic Brain Injury & Concussion (CDC).

December 1, 2017 Posted by | Lectures, Medicine, Neurology | Leave a comment

Acute Coronary Syndromes

A few quotes from the lecture, as well as some links to related stuff:

“You might say: Why doesn’t coronary stenting prevent heart attacks? You got an 80 % blockage causing some angina and you stent it, why doesn’t that prevent a heart attack? And the answer is very curious. The plaques that are most likely to rupture are mild. They’re typically less than 50 %. They have a thin fibrous cap, a lot of lipid, and they rupture during stress. This has been the real confusion for my specialty over the last 30 years, starting to realize that, you know, when you get angina we find the blockage and we fix it and your angina’s better, but the lesions that were gonna cause next week’s heart attack often are not the lesion we fixed, but there’s 25 other moderate plaques in the coronary tree and one of them is heating up and it’s vulnerable. […] ACS, the whole thing here is the idea of a vulnerable plaque rupture. And it’s often not a severe narrowing.” (3-5 minutes in)

[One of the plaque rupture triggers of relevance is inflammatory cytokines…] “What’s a good example of that? Influenza. Right, influenza releases things like, IL-6 and other cytokines. What do they do? Well, they make you shake and shiver and feel like your muscles are dying. They also dissolve plaques. […] If you take a town like Ann Arbor and vaccinate everybody for influenza, we reduce heart attacks by a lot … 20-30 % during flu season.” (~11-12 minutes in)

“What happens to your systolic function as you get older? Any ideas? I’m happy to tell you it stays strong. […] What happens to diastole? […] As your myocardial cells die, a few die every day, […] those cells get replaced by fibrous tissue. So an aging heart becomes gradually stiffer [this is apparently termed ‘presbycardia’]. It beats well because the cells that are alive can overcome the fibrosis and squeeze, but it doesn’t relax as well. So left ventricular and diastolic pressure goes up. Older patients are much more likely to develop heart failure [in the ACS setting] because they already have impaired diastole from […] presbycardia.” (~1.14-1.15)

Some links to coverage of topics covered during the lecture:

Acute Coronary Syndrome.
Unstable angina.
Pathology of Acute Myocardial Infarction.
Acute Coronary Syndrome Workup.
Acute Coronary Syndrome Treatment & Management.
The GRACE risk score.
Complications of Myocardial Infarction.
Early versus Delayed Invasive Intervention in Acute Coronary Syndromes (Mehta et al. 2009).

November 3, 2017 Posted by | Cardiology, Lectures, Medicine, Studies | Leave a comment

The mystery of over-parametrization in neural networks


October 6, 2017 Posted by | Computer science, Lectures, Mathematics | Leave a comment

National EM Board Review Course: Toxicology

Some links:

Alcoholic Ketoacidosis.
Gastrointestinal decontamination in the acutely poisoned patient.
Chelation in Metal Intoxication.
Mudpiles – causes of high anion-gap metabolic acidosis.
Whole-bowel irrigation: Background, indications, contraindications…
Organophosphate toxicity.
Withdrawal syndromes.
Acetaminophen toxicity.
Alcohol withdrawal.
Wernicke syndrome.
Methanol toxicity.
Ethylene glycol toxicity.
Sympathomimetic toxicity.
Disulfiram toxicity.
Arsenic toxicity.
Barbiturate toxicity.
Beta-blocker toxicity.
Calcium channel blocker toxicity.
Carbon monoxide toxicity.
Caustic ingestions.
Clonidine toxicity.
Cyanide toxicity.
Digitalis toxicity.
Gamma-hydroxybutyrate toxicity.
Hydrocarbon toxicity.
CDC Facts About Hydrogen Fluoride (Hydrofluoric Acid).
Hydrogen Sulfide Toxicity.
Isoniazid toxicity.
Iron toxicity.
Lead toxicity.
Lithium toxicity.
Mercury toxicity.
Mushroom toxicity.
Gyromitra mushroom toxicity.
Neuroleptic agent toxicity.
Neuroleptic malignant syndrome.
Oral hypoglycemic agent toxicity.
PCP toxicity.
Phenytoin toxicity.
Rodenticide toxicity.
Salicylate toxicity.
Serotonin syndrome.
TCA toxicity.

September 29, 2017 Posted by | Lectures, Medicine, Pharmacology, Psychiatry | Leave a comment

National EM Board Review Course: Environmental Emergencies

Some links to resources on stuff covered in the lecture:

Diving disorders.
Henry’s law/Boyle’s law/Dalton’s law.
Nitrogen narcosis.
Decompression Sickness.
Hyperbaric Oxygen Therapy.
Blast Injuries.
Altitude sickness.
High Altitude Flatus Expulsion (HAFE).
High-Altitude Pulmonary Edema.
Cold-induced vasodilation.
Osborn Waves.
Frostbite (‘think of this as a thermal burn equivalent caused by cold’).
Trench foot.
Heat stroke.
Heat cramps.
Thermal Burns.
Parkland formula.
Escharotomy and Burns.
Electrical Injuries in Emergency Medicine.
Lightning Injuries.
Radiation exposure.
Inhalation Anthrax.
Botulism As a Bioterrorism Agent.
Chemical weapon/vessicants/nerve agent.
Bite injuries.
Cat scratch disease.
Rattlesnake Bite.
Snakebites: First aid.
Snake bite: coral snakes.
Black widow spider bite.
Brown recluse spider bite.
Marine envenomation.

September 22, 2017 Posted by | Lectures, Medicine | Leave a comment

Ophthalmology – National EM Board Review Course

The lecture covers a lot of different stuff. Some links:

Orbital Cellulitis.
Cranial Nerves III, IV, and VI: The Oculomotor System.
Argyll Robertson pupil.
Marcus Gunn pupil.
Horner syndrome.
Third nerve palsy.
Homonymous hemianopsia.
Central Retinal Artery Occlusion.
Central Retinal Vein Occlusion.
Optic Neuritis.
Retinal detachment.
Temporal Arteritis.
Epidemic Keratoconjunctivitis (EKC).
Herpes Zoster Ophthalmicus.
Subconjunctival Hemorrhage.
Corneal Abrasion.
Corneal Laceration.
Globe Rupture.
Acute Angle-Closure Glaucoma.
Retrobulbar hemorrhage.

September 15, 2017 Posted by | Lectures, Medicine, Ophthalmology, Pharmacology | Leave a comment

Gastroenterology – Amal Mattu

If I hadn’t just read Horowitz & Samsom’s book I’m fairly sure this lecture would have been difficult to follow, but a lot of the stuff covered here is (naturally) closely related to the stuff covered in that book; this is mostly a revision lecture aimed at reminding you of stuff you already (supposedly?) know and/or dealing with topics closely related to stuff you already know, I don’t think it’s the right lecture for someone who knows very little about gastroenterology. I like Mattu’s approach to lecturing; this lecture was both fun and enjoyable to watch, despite (?) including a lot of information.

A few links to stuff covered/mentioned in the lecture:

Boerhaave syndrome.
Does This Patient Have a Severe Upper Gastrointestinal Bleed? (JAMA).
Acute Liver Failure (NEJM review article).
Charcot’s cholangitis triad.
Ranson criteria.
Crohn’s disease.
Ulcerative colitis.
Abdominal aortic aneurysm.
Mesenteric ischemia.
Shigella infection.
Clostridium perfringens.
Pseudomembranous colitis.

September 11, 2017 Posted by | Gastroenterology, Lectures, Medicine, Microbiology | Leave a comment

Interactive Coding with “Optimal” Round and Communication Blowup

The youtube description of this one was rather longer than usual, and I decided to quote it in full below:

“The problem of constructing error-resilient interactive protocols was introduced in the seminal works of Schulman (FOCS 1992, STOC 1993). These works show how to convert any two-party interactive protocol into one that is resilient to constant-fraction of error, while blowing up the communication by only a constant factor. Since these seminal works, there have been many follow-up works which improve the error rate, the communication rate, and the computational efficiency. All these works assume that in the underlying protocol, in each round, each party sends a *single* bit. This assumption is without loss of generality, since one can efficiently convert any protocol into one which sends one bit per round. However, this conversion may cause a substantial increase in *round* complexity, which is what we wish to minimize in this work. Moreover, all previous works assume that the communication complexity of the underlying protocol is *fixed* and a priori known, an assumption that we wish to remove. In this work, we consider protocols whose messages may be of *arbitrary* lengths, and where the length of each message and the length of the protocol may be *adaptive*, and may depend on the private inputs of the parties and on previous communication. We show how to efficiently convert any such protocol into another protocol with comparable efficiency guarantees, that is resilient to constant fraction of adversarial error, while blowing up both the *communication* complexity and the *round* complexity by at most a constant factor. Moreover, as opposed to most previous work, our error model not only allows the adversary to toggle with the corrupted bits, but also allows the adversary to *insert* and *delete* bits. In addition, our transformation preserves the computational efficiency of the protocol. Finally, we try to minimize the blowup parameters, and give evidence that our parameters are nearly optimal. This is joint work with Klim Efremenko and Elad Haramaty.”

A few links to stuff covered/mentioned in the lecture:

Coding for interactive communication correcting insertions and deletions.
Efficiently decodable insertion/deletion codes for high-noise and high-rate regimes.
Common reference string model.
Small-bias probability spaces: Efficient constructions and applications.
Interactive Channel Capacity Revisited.
Collision (computer science).
Chernoff bound.

September 6, 2017 Posted by | Computer science, Cryptography, Lectures, Mathematics | Leave a comment

Utility of Research Autopsies for Understanding the Dynamics of Cancer

A few links:
Pancreatic cancer.
Jaccard index.
Limited heterogeneity of known driver gene mutations among the metastases of individual patients with pancreatic cancer.
Tissue-specific mutation accumulation in human adult stem cells during life.
Epigenomic reprogramming during pancreatic cancer progression links anabolic glucose metabolism to distant metastasis.

August 25, 2017 Posted by | Cancer/oncology, Genetics, Immunology, Lectures, Medicine, Statistics | Leave a comment

Quantifying tumor evolution through spatial computational modeling

Two general remarks: 1. She talks very fast, in my opinion unpleasantly fast – the lecture would have been at least slightly easier to follow if she’d slowed down a little. 2. A few of the lectures uploaded in this lecture series (from the IAS Mathematical Methods in Cancer Evolution and Heterogeneity Workshop) seem to have some sound issues; in this lecture there are multiple 1-2 seconds long ‘chunks’ where the sound drops out and some words are lost. This is really annoying, and a similar problem (which was likely ‘the same problem’) previously lead me to quit another lecture in the series; however in this case I decided to give it a shot anyway, and I actually think it’s not a big deal; the sound-losses are very short in duration, and usually no more than one or two words are lost so you can usually figure out what was said. During this lecture there was incidentally also some issues with the monitor roughly 27 minutes in, but this isn’t a big deal as no information was lost and unlike the people who originally attended the lecture you can just skip ahead approximately one minute (that was how long it took to solve that problem).

A few relevant links to stuff she talks about in the lecture:

A Big Bang model of human colorectal tumor growth.
Approximate Bayesian computation.
Site frequency spectrum.
Identification of neutral tumor evolution across cancer types.
Using tumour phylogenetics to identify the roots of metastasis in humans.

August 22, 2017 Posted by | Cancer/oncology, Evolutionary biology, Genetics, Lectures, Mathematics, Medicine, Statistics | Leave a comment

Epilepsy Diagnosis & Treatment – 5 New Things Every Physician Should Know

Links to related stuff:
i. Sudden unexpected death in epilepsy (SUDEP).
ii. Status epilepticus.
iii. Epilepsy surgery.
iv. Temporal lobe epilepsy.
v. Lesional epilepsy surgery.
vi. Nonlesional neocortical epilepsy.
vii. A Randomized, Controlled Trial of Surgery for Temporal-Lobe Epilepsy.
viii. Stereoelectroencephalography.
ix. Accuracy of intracranial electrode placement for stereoencephalography: A systematic review and meta-analysis. (The results of the review is not discussed in the lecture, for obvious reasons – lecture is a few years old, this review is brand new – but seemed relevant to me.)
x. MRI-guided laser ablation in epilepsy treatment.
xi. Laser thermal therapy: real-time MRI-guided and computer-controlled procedures for metastatic brain tumors.
xii. Critical review of the responsive neurostimulator system for epilepsy (Again, not covered but relevant).
xiii. A Multicenter, Prospective Pilot Study of Gamma Knife Radiosurgery for Mesial Temporal Lobe Epilepsy: Seizure Response, Adverse Events, and Verbal Memory.
xiv. Gamma Knife radiosurgery for recurrent or residual seizures after anterior temporal lobectomy in mesial temporal lobe epilepsy patients with hippocampal sclerosis: long-term follow-up results of more than 4 years (Not covered but relevant).

July 19, 2017 Posted by | Lectures, Medicine, Neurology, Studies | Leave a comment

Detecting Cosmic Neutrinos with IceCube at the Earth’s South Pole

I thought there were a bit too many questions/interruptions for my taste, mainly because you can’t really hear the questions posed by the members of the audience, but aside from that it’s a decent lecture. I’ve added a few links below which covers some of the topics discussed in the lecture.

Neutrino astronomy.
Antarctic Impulse Transient Antenna (ANITA).
Neutral pion decays.
IceCube Neutrino Observatory.
Evidence for High-Energy Extraterrestrial Neutrinos at the IceCube Detector (Science).
Atmospheric and astrophysical neutrinos above 1 TeV interacting in IceCube.
Notes on isotropy.
Measuring the flavor ratio of astrophysical neutrinos.
Supernova 1987A neutrino emissions.

July 18, 2017 Posted by | Astronomy, Lectures, Physics, Studies | Leave a comment

Probing the Early Universe through Observations of the Cosmic Microwave Background

This lecture/talk is a few years old, but it was only made public on the IAS channel last week (…along with a lot of other lectures – the IAS channel has added a lot of stuff recently, including more than 150 lectures within the last week or so; so if you’re interested you should go have a look).

Below the lecture I have added a few links with stuff (wiki-articles and a few papers) related to the topics covered in the lecture. I didn’t read those links, but I skimmed them (and a few others, which I subsequently decided not to include as their coverage did not overlap sufficiently with the stuff covered in the lecture) and decided to add them in order to remind myself what kind of stuff was included in the lecture/allow others to infer what kind of stuff might be included in the lecture. The links naturally go into a lot more detail than does the lecture, but these are the sort of topics discussed/included.

The lecture is long (90 minutes + a short Q&A), but it was interesting enough for me to watch all of it. The lecturer displays a very high level of speech disfluency throughout the lecture, in the sense that I might not be surprised if I were told that the most commonly word encountered during this lecture was ‘um’ or ‘uh’, rather than more commonly encountered mode words like ‘the’, but you get used to it (at least I managed to sort of ‘tune it out’ after a while). I should caution that there’s a short ‘jump’ very early on in the lecture (at the 2 minute mark or so) where a small amount of frames were apparently dropped, but that should not scare you away from watching the lecture; that frame drop is the only one of its kind during the lecture, aside from a similar brief ‘jump’ around the 1 hour 9 minute mark.

Some links:

Astronomical interferometer.
Fourier transform.
Boomerang : A Balloon-borne Millimeter Wave Telescope and Total Power Receiver for Mapping Anisotropy in the Cosmic Microwave Background.
Observations of the Temperature and Polarization Anisotropies with Boomerang 2003.
Detection of the Power Spectrum of Cosmic Microwave Background Lensing by the Atacama Cosmology Telescope.
Secondary anisotropies of the CMB (review article).
Planck early results. VIII. The all-sky early Sunyaev-Zeldovich cluster sample.
Sunyaev–Zel’dovich effect.
A CMB Polarization Primer.
Spider: a balloon-borne CMB polarimeter for large angular scales.

July 13, 2017 Posted by | Astronomy, cosmology, Lectures, Physics | Leave a comment

Melanoma therapeutic strategies that select against resistance

A short lecture, but interesting:

If you’re not an oncologist, these two links in particular might be helpful to have a look at before you start out: BRAF (gene) & Myc. A very substantial proportion of the talk is devoted to math and stats methodology (which some people will find interesting and others …will not).

July 3, 2017 Posted by | Biology, Cancer/oncology, Genetics, Lectures, Mathematics, Medicine, Statistics | Leave a comment