Structure and Randomness in Combinatorics

Terence Tao

Type: Article

Publication Date: 2007-10-01

Citations: 14

DOI: https://doi.org/10.1109/focs.2007.4389475

Abstract

Combinatorics, like computer science, often has to deal with large objects of unspecified (or unusable) structure. One powerful way to deal with such an arbitrary object is to decompose it into more usable components. In particular, it has proven profitable to decompose such objects into a structured component, a pseudo-random component, and a small component (i.e. an error term): in many cases it is the structured component which then dominates. We illustrate this philosophy in a number of model cases.

Locations

Annual Symposium on Foundations of Computer Science - View
arXiv (Cornell University) - PDF
arXiv (Cornell University) - View - PDF
Annual Symposium on Foundations of Computer Science - View
arXiv (Cornell University) - PDF
arXiv (Cornell University) - View - PDF
Annual Symposium on Foundations of Computer Science - View
arXiv (Cornell University) - PDF
arXiv (Cornell University) - View - PDF

Similar Works

Action	Title	Year	Authors
+ PDF Chat	Structure and Randomness in Combinatorics	2007	Terence Tao
+	Structure and randomness in combinatorics	2007	Terence Tao
+	Combinatorics: Steps toward a Unified Theory	1974	Gina Kolata
+	Combinatorics: Trends and Examples	1982	Kenneth Bacławski
+	Combinatorics and Computer Science	1996	Michel Deza Reinhardt Euler Ioannis Manoussakis
+	Principles of Combinatorics.	1972	Gian‐Carlo Rota C. Berge
+	Principles of Combinatorics	2020	David Mazur
+	Principles of Combinatorics	1971
+	Theory and practice of combinatories: A collection of articles honoring Anton Kotzig on the occasion of his sixtieth birthday	1983
+	Theory and Practice of Combinatorics	1983	Roger Knott A. Rosa G. Sabidussi J. Turgeon
+	Principles and Techniques in Combinatorics	1992	Chuan-Chong Chen Koh Khee-Meng
+	Principles and Techniques in Combinatorics	1999	Steve Abbott Chen Chuang-Chong Koh Khee-Meng
+	Principles and Techniques in Combinatorics	2018	Kean Pew Foo Simon Lin Mingyan
+	Stratified approach in combinatorics	1999	Min Yan Bei-Fang Chen
+ PDF	Combinatorics and Physics	2011	Christian Brouder Frédéric Patras
+	Interview with Richard P. Stanley: The Wonderful World of Combinatorics	2022	Shaoshi Chen
+	Combinatorics	2008	John Harris Jeffry L. Hirst Michael J. Mossinghoff
+ PDF	On usage of operators in combinatorics : construction, analysis and random generation	2016	Nicolas Rolin
+	- Sequences in combinatorics	2015
+	Combinatory Analysis	1917

Works That Cite This (12)

Action	Title	Year	Authors
+	Large values of the Gowers-Host-Kra seminorms	2010	Tanja Eisner Terence Tao
+	The inverse conjecture for the Gowers norm over finite fields in low characteristic	2011	Terence Tao Tamar Ziegler
+	The distribution of polynomials over finite fields, with applications to the Gowers norms	2007	Ben Green Terence Tao
+ PDF Chat	An Arithmetic Regularity Lemma, An Associated Counting Lemma, and Applications	2010	Ben Green Terence Tao
+ PDF	Higher-order Fourier Analysis and Applications	2019	Hamed Hatami Pooya Hatami Shachar Lovett
+ PDF Chat	The Inverse Conjecture for the Gowers Norm over Finite Fields in Low Characteristic	2011	Terence Tao Tamar Ziegler
+ PDF	Three Topics in Additive Prime Number Theory	2007	Ben Green
+	Further cryptographic properties of the multiplicative inverse function	2021	Deng Tang Bimal Mandal Subhamoy Maitra
+	$L_p$ regular sparse hypergraphs	2015	Pandelis Dodos Vassilis Kanellopoulos Thodoris Karageorgos
+	Turing machine algorithms and studies in quasi-randomness	2011	Subrahmanyam Kalyanasundaram

Works Cited by This (15)

Action	Title	Year	Authors
+	Recurrence in Ergodic Theory and Combinatorial Number Theory	1981	Harry Furstenberg
+ PDF Chat	The ergodic and combinatorial approaches to Szemerédi’s theorem	2007	Terence Tao
+ PDF Chat	The Gaussian primes contain arbitrarily shaped constellations	2006	Terence Tao
+ PDF	A Quantitative Ergodic Theory Proof of Szemerédi's Theorem	2006	Terence Tao
+	Norm convergence of multiple ergodic averages for commuting transformations	2007	Terence Tao
+	A correspondence principle between (hyper)graph theory and probability theory, and the (hyper)graph removal lemma	2006	Terence Tao
+	Quick Approximation to Matrices and Applications	1999	Alan Frieze Ravi Kannan
+	On the Littlewood problem modulo a prime	2006	Ben Green Sergeĭ Konyagin
+ PDF	The primes contain arbitrarily long arithmetic progressions	2008	Benjamin Green Terence Tao
+	Quasirandomness, Counting and Regularity for 3-Uniform Hypergraphs	2006	W. T. Gowers