A Theorist's Toolkit

This lecture provides foundational guidance for graduate-level research in theoretical computer science, discussing essential mathematical and computational concepts. It outlines key texts and academic practices relevant to embarking on a career as a TCS researcher.

This lecture introduces heuristic approaches and 'street fighting' techniques for tackling challenging mathematical problems, focusing on practical methods and intuition relevant to theoretical computer science research. It emphasizes problem deconstruction and approximation strategies.

This lecture introduces the formal definitions and applications of Big O, Big Omega, Little O, and Little Omega notation, alongside related asymptotic forms such as poly() and O-tilde. It references foundational texts including 'Asymptopia' and 'Concrete Mathematics' for rigorous mathematical treatment.

This lecture from CMU's graduate CS Theory Toolkit rigorously derives the asymptotic behavior of the nth harmonic number H_n, employing both elementary series manipulation and the integral approximation method. It references seminal texts in discrete mathematics and asymptotic analysis.

This graduate-level lecture from CMU's CS Theory Toolkit details techniques for asymptotic analysis, including approximations for exponential functions, converting expressions to standard forms, and minimizing functions with parameters.

Asymptotics of the Central Binomial Coefficient. Recitation 1 of "CS Theory Toolkit": a semester-long graduate course on math and CS fundamentals for research in theoretical computer science, taught at Carnegie Mellon University.

This lecture analyzes the asymptotic behavior of the Birthday Paradox, determining the number of items needed to achieve a 1/2 probability of collision when distributed into a fixed number of bins. It references foundational texts in combinatorics and asymptotic analysis.

This lecture delves into the asymptotic analysis of n!, providing a partial proof and statement of Stirling's Formula. It references 'Asymptopia' by Joel Spencer.

This session examines the asymptotic behavior of binomial coefficients, 'n choose k', incorporating a detailed discussion of the binary entropy function. Essential for probability analysis.

This lecture provides a rigorous statement of the Central Limit Theorem, covering sums of independent random variables and standardization techniques.

This lecture investigates the fundamental properties of Gaussian random variables, elucidating 'The Fact' from which many of their characteristics are derived.

This lecture introduces the Berry --Esseen Theorem, presenting it as a practical extension of the Central Limit Theorem that provides explicit error bounds for approximation accuracy.

This lecture details Markov's and Chebyshev's Inequalities, or the First and Second Moment Methods, for bounding tail probabilities given only means or variances.

This lecture delivers a proof of Chernoff's Bound for large deviations, focusing on the simple case of sums of independent fair coin flips.

This session outlines the general statements of Chernoff and Hoeffding bounds, exploring concepts like negative association and the 'Sampling Theorem' for estimating means.

This lecture formally introduces Turing Machines as a foundational computational model, laying the groundwork for understanding computability and complexity.

This lecture explores Boolean circuits as a computational model, delving into circuit classes, upper and lower bounds, and the concepts of uniformity and non-uniformity.

This lecture presents the Word RAM model for algorithm analysis, specifically addressing the complexity of sorting integers within this computational framework.