Skip to primary content
Skip to secondary content

in theory

"Marge, I agree with you – in theory. In theory, communism works. In theory." — Homer Simpson

in   theory

Main menu

  • Home
  • About
  • LaTeX to WordPress
    • Download
    • LaTeX2WP Example
    • Using LaTeX2WP
  • Lecture Notes

Tag Archives: Chernoff bounds

CS359G Lecture 18: Properties of Expanders

Posted on March 16, 2011 by luca
3

In which we prove properties of expander graphs.

Continue reading →

Posted in CS359G | Tagged Chernoff bounds, Expanders, random walks | 3 Replies

CS254 Lecture 4 – The Polynomial Hierarchy

Posted on April 25, 2010 by luca
2

Today we show how to reduce the error probability of probabilistic algorithms, prove Adleman’s theorem that polynomial time probabilistic algorithms can be simulated by polynomial size circuits, and we give the definition of the polynomial hierarchy

Continue reading →

Posted in CS254 | Tagged Chernoff bounds, CS254 2010, polynomial hierarchy | 2 Replies
Follow in theory on WordPress.com

Recent Comments

  • B. on Workshop on Fairness in AI
  • abc def on Workshop in Milan Next Week
  • luca on Workshop in Milan Next Week
  • abc def on Workshop in Milan Next Week
  • Workshop in Milan Next Week | in theory on STOC 2022, and other theory events

Recent Posts

  • Workshop on Fairness in AI
  • Workshop in Milan Next Week
  • The First XL Computer Scientist
  • STOC 2022, and other theory events
  • Renato Capocelli (1940-1992)

Archives

Categories

  • Additive Combinatorics
  • Apple
  • ARV
  • average-case complexity
  • Avi Wigderson
  • Ben Green
  • CCA security
  • Cheeger inequality
  • circuit lower bounds
  • Conceptual contributions
  • covid-19
  • cryptography
  • CS254 2010
  • Dan Spielman
  • eigenvalues
  • eigenvectors
  • Expanders
  • Fields Medal
  • FOCS 2006
  • FOCS 2010
  • Graph Isomorphism
  • Hard-Core Sets
  • ICM 2006
  • Integrality gap
  • Jean Bourgain
  • jobs
  • Laplacian
  • LaTeX in WordPress
  • Leonid Levin
  • linear programming
  • Luby-Rackoff
  • MAC
  • Max Cut
  • maximum flow
  • Metric embeddings
  • Moses Charikar
  • Natural Proofs
  • Notices of the AMS
  • Oded Goldreich
  • online optimization
  • Paul Erdos
  • PCP
  • Proposition 8
  • pseudorandom function
  • Pseudorandomness
  • pseudorandom permutation
  • public-key encryption
  • quadratic residue
  • Random Oracle Model
  • random walks
  • Regularity Lemma
  • RSA
  • Russell Impagliazzo
  • safety
  • SAT
  • semidefinite programming
  • signature schemes
  • Silvio Micali
  • sparsest cut
  • spectral graph theory
  • Spectral partitioning
  • Stephen Colbert
  • STOC and FOCS
  • stochastic block model
  • Szemeredi Theorem
  • Tamar Ziegler
  • Terence Tao
  • things that are excellent
  • things that are terrible
  • Tim Gowers
  • Turing Centennial
  • unique games
  • World Cup
  • Zero Knowledge
  • zig-zag product

Top Posts

  • LaTeX to WordPress
  • Lecture Notes
  • Turing Centennial Post 7: Ashwin Nayak
  • Download
  • About
  • The Impagliazzo Hard-Core-Set Theorem
  • The Power Method
  • Converting LaTeX to WordPress
  • Two recent papers by Cui Peng
  • The spectrum of the infinite tree

math

  • Doron Zeilberger
  • Terry Tao
  • Tim Gowers

non-theory

  • Bitch PhD
  • The Peking Duck
  • Unfogged

theory

  • 3D Pancakes
  • Complexity Blog
  • Geomblog
  • Informatics Weekly
  • James Lee
  • My Biased Coin
  • my slice of pizza
  • Oded Goldreich
  • Process Algebra Diary
  • Richard Lipton
  • Shtetl Optimized
  • Theory Matters

Recent Comments

B. on Workshop on Fairness in A…
abc def on Workshop in Milan Next We…
luca on Workshop in Milan Next We…
abc def on Workshop in Milan Next We…
Workshop in Milan Ne… on STOC 2022, and other theory…

math

  • Doron Zeilberger
  • Terry Tao
  • Tim Gowers

non-theory

  • Bitch PhD
  • The Peking Duck
  • Unfogged

theory

  • 3D Pancakes
  • Complexity Blog
  • Geomblog
  • Informatics Weekly
  • James Lee
  • My Biased Coin
  • my slice of pizza
  • Oded Goldreich
  • Process Algebra Diary
  • Richard Lipton
  • Shtetl Optimized
  • Theory Matters

Archives

Categories

  • Additive Combinatorics
  • Apple
  • ARV
  • average-case complexity
  • Avi Wigderson
  • Ben Green
  • CCA security
  • Cheeger inequality
  • circuit lower bounds
  • Conceptual contributions
  • covid-19
  • cryptography
  • CS254 2010
  • Dan Spielman
  • eigenvalues
  • eigenvectors
  • Expanders
  • Fields Medal
  • FOCS 2006
  • FOCS 2010
  • Graph Isomorphism
  • Hard-Core Sets
  • ICM 2006
  • Integrality gap
  • Jean Bourgain
  • jobs
  • Laplacian
  • LaTeX in WordPress
  • Leonid Levin
  • linear programming
  • Luby-Rackoff
  • MAC
  • Max Cut
  • maximum flow
  • Metric embeddings
  • Moses Charikar
  • Natural Proofs
  • Notices of the AMS
  • Oded Goldreich
  • online optimization
  • Paul Erdos
  • PCP
  • Proposition 8
  • pseudorandom function
  • Pseudorandomness
  • pseudorandom permutation
  • public-key encryption
  • quadratic residue
  • Random Oracle Model
  • random walks
  • Regularity Lemma
  • RSA
  • Russell Impagliazzo
  • safety
  • SAT
  • semidefinite programming
  • signature schemes
  • Silvio Micali
  • sparsest cut
  • spectral graph theory
  • Spectral partitioning
  • Stephen Colbert
  • STOC and FOCS
  • stochastic block model
  • Szemeredi Theorem
  • Tamar Ziegler
  • Terence Tao
  • things that are excellent
  • things that are terrible
  • Tim Gowers
  • Turing Centennial
  • unique games
  • World Cup
  • Zero Knowledge
  • zig-zag product

Top Posts

  • LaTeX to WordPress
  • Lecture Notes
  • Turing Centennial Post 7: Ashwin Nayak
  • Download
  • About
  • The Impagliazzo Hard-Core-Set Theorem
  • The Power Method
  • Converting LaTeX to WordPress
  • Two recent papers by Cui Peng
  • The spectrum of the infinite tree
Blog at WordPress.com.
  • Follow Following
    • in theory
    • Join 609 other followers
    • Already have a WordPress.com account? Log in now.
    • in theory
    • Customize
    • Follow Following
    • Sign up
    • Log in
    • Report this content
    • View site in Reader
    • Manage subscriptions
    • Collapse this bar