Symposium on Visions of the Theory of Computing 2013
2013-05-29..2013-05-31
Berkeley, United States
who it's for
theoretical computer scientists, machine learning researchers, computational neuroscientists, quantum computing researchers, computational biologists, cryptographers, data scientists, algorithm designers
topics
computational models of cortex; quantum supremacy and Majorana hardware; diffusive influence systems; sequence graphs for genomes; strong perfect graph theorem; social cascade and hotspot models; zero-knowledge and verifiable computation; statistical physics of random k-SAT; streaming algorithms: Count-Min and L0 sampling; sparse distributed representations and sequence memory; online learning platforms and MOOC design; DNA nanotechnology self-assembly
| title | author | length |
|---|---|---|
| What Should a Computational Theory of Cortex Explain? | Leslie Valiant | 57m |
Argues a concrete cortical model with three resource parameters (n, d, K) and local neuron programs, formalizes operations: hierarchical memorization… | ||
| Quantum Computing and the Entanglement Frontier | John Preskill | 01h 00m |
Argues that scaling into the entanglement frontier promises genuine quantum supremacy for tasks like simulating quantum field theory and running Shor’s… | ||
| Why Biology is Different | Bernard Chazelle | 46m |
Claims that diffusive influence systems are almost surely asymptotically periodic yet can encode chaos and Turing machines on fractal, measure-zero Cantor… | ||
| Big Data and New Models Needed to Study DNA Variation in Evolution and Cancer | David Haussler | 57m |
Project aims to sequence 10,000 vertebrate genomes and turn tissues into iPS-derived cortical neurospheres, then use RNA‑seq and chromatin assays to pinpoint… | ||
| Perfection and Beyond | Maria Chudnovsky | 49m |
Describes the proof that Strong Perfect Graph Theorem holds via a triple of results: classify Berge graphs as five basic classes (bipartite, complements… | ||
| Bursts, Cascades, and Hot Spots: Algorithmic Models of Social Phenomena | Jon Kleinberg | 01h 15m |
Uses geotagged Flickr photos (2009) and a mean shift density search plus Bayes‑style tag scoring to find hotspots at 100 km and 100 m scales, producing the top… | ||
| The Cryptographic Lens: Visions of our Past and Future | Shafi Goldwasser | 57m |
Cryptography reframes theory: zero-knowledge proofs let a verifier be convinced without learning a witness; interactive proofs expand verification power… | ||
| "More is Different." Also in Computing? | Marc Mézard | 01h 04m |
Argues that statistical‑physics tools (replica/cavity/mean‑field) yield concrete, testable claims: random k‑SAT has a sharp threshold at alpha_c ≈ 4.2667… | ||
| Theory of Data Streams | S. Muthu Muthukrishnan | 55m |
Describes two concrete streaming primitives and what they actually achieve: Count-Min Sketch uses O(1/ε · log(1/δ)) counters, O(log(1/δ)) update time, and… | ||
| Intelligence and Machines: Creating Intelligent Machines By Modeling the Brain | Jeff Hawkins | 59m |
Claim: intelligence is the ability to learn a sensory‑motor model of the world by implementing neocortical principles. Implements sparse distributed… | ||
| The Online Revolution: Learning Without Limits | Daphne Koller | 57m |
A global platform is spun out from Stanford in 2012 and grows to partner with ~70 universities offering 374 courses to 3.7 million learners, with early courses… | ||
| Programming Nanoscale Structure Using DNA-Based Information | Ned Seeman | 58m |
Describes programmable DNA motifs that produce working structures: 32 nm stripe spacing appears in AFM for DX 2D lattices; triangular DNA motifs self-assemble… | ||
| Consumer Behavior and Algorithm Design | Prabhakar Raghavan | 58m |
Claims that consumer-facing computing reshapes algorithms and gives concrete wins: a web adjacency scheme compresses links to about three bits per edge (MSR… | ||
| Market Design and Computer-Assisted Markets: An Economist's Perspective | Alvin Roth | 56m |
Shows that running a deferred acceptance algorithm by phone with a fixed 7‑hour selection day creates congestion: offers take five minutes and rejections one… | ||
| Evolution and Computation | Christos Papadimitriou | 01h 03m |
Claim: under weak selection classical Fisher‑Wright population genetics is equivalent to a repeated game run by genes using the multiplicative weights update… | ||
| The Mathematics of Causal Inference, with Reflections on Machine Learning and the Logic of Science | Judea Pearl | 01h 01m |
Argues that causal questions require structural models, not just distributions, and gives concrete tools: structural equations, graphs and do-calculus with… | ||
| The Gospel According to TCS | Avi Wigderson | 01h 01m |
Survey of core theoretical computer science claims that maps concrete tools to outcomes: polynomial-time reductions and NP-complete gadgets explain why… | ||
| The Modern Astrophysics Stack: Automated Action and Insight | Josh Bloom | 01h 04m |
Describes an automated end-to-end pipeline: robotic telescopes that slew to GRBs within a minute, a survey ingesting 1.5 million nightly candidates that… | ||
| nothing matches | ||