Analysis of Boolean Functions

Cambridge University Press
Free sample

Boolean functions are perhaps the most basic objects of study in theoretical computer science. They also arise in other areas of mathematics, including combinatorics, statistical physics, and mathematical social choice. The field of analysis of Boolean functions seeks to understand them via their Fourier transform and other analytic methods. This text gives a thorough overview of the field, beginning with the most basic definitions and proceeding to advanced topics such as hypercontractivity and isoperimetry. Each chapter includes a 'highlight application' such as Arrow's theorem from economics, the Goldreich–Levin algorithm from cryptography/learning theory, Håstad's NP-hardness of approximation results, and 'sharp threshold' theorems for random graph properties. The book includes roughly 450 exercises and can be used as the basis of a one-semester graduate course. It should appeal to advanced undergraduates, graduate students and researchers in computer science theory and related mathematical fields.
Read more

About the author

Ryan O'Donnell is an Associate Professor in the Computer Science Department at Carnegie Mellon University.

Read more

Reviews

Loading...

Additional Information

Publisher
Cambridge University Press
Read more
Published on
Jun 5, 2014
Read more
Pages
445
Read more
ISBN
9781139952507
Read more
Language
English
Read more
Genres
Computers / Computer Science
Computers / General
Mathematics / Combinatorics
Mathematics / Discrete Mathematics
Mathematics / General
Science / Physics / General
Read more
Content Protection
This content is DRM protected.
Read more
Read Aloud
Available on Android devices
Read more

Reading information

Smartphones and Tablets

Install the Google Play Books app for Android and iPad/iPhone. It syncs automatically with your account and allows you to read online or offline wherever you are.

Laptops and Computers

You can read books purchased on Google Play using your computer's web browser.

eReaders and other devices

To read on e-ink devices like the Sony eReader or Barnes & Noble Nook, you'll need to download a file and transfer it to your device. Please follow the detailed Help center instructions to transfer the files to supported eReaders.
Titu Andreescu
Number theory, an ongoing rich area of mathematical exploration, is noted for its theoretical depth, with connections and applications to other fields from representation theory, to physics, cryptography, and more. While the forefront of number theory is replete with sophisticated and famous open problems, at its foundation are basic, elementary ideas that can stimulate and challenge beginning students. This lively introductory text focuses on a problem-solving approach to the subject.

Key features of Number Theory: Structures, Examples, and Problems:

* A rigorous exposition starts with the natural numbers and the basics.

* Important concepts are presented with an example, which may also emphasize an application. The exposition moves systematically and intuitively to uncover deeper properties.

* Topics include divisibility, unique factorization, modular arithmetic and the Chinese Remainder Theorem, Diophantine equations, quadratic residues, binomial coefficients, Fermat and Mersenne primes and other special numbers, and special sequences. Sections on mathematical induction and the pigeonhole principle, as well as a discussion of other number systems are covered.

* Unique exercises reinforce and motivate the reader, with selected solutions to some of the problems.

* Glossary, bibliography, and comprehensive index round out the text.

Written by distinguished research mathematicians and renowned teachers, this text is a clear, accessible introduction to the subject and a source of fascinating problems and puzzles, from advanced high school students to undergraduates, their instructors, and general readers at all levels.

©2018 GoogleSite Terms of ServicePrivacyDevelopersArtistsAbout Google
By purchasing this item, you are transacting with Google Payments and agreeing to the Google Payments Terms of Service and Privacy Notice.