Main.AdditiveCombinatoricsMinicourse History
Hide minor edits - Show changes to markup
May 01, 2008, at 11:16 AM
by 75.196.94.215 -
Changed lines 8-9 from:
were given in the course. click here for lecture notes of the course (this the is first draft of the notes - stay tuned for updated versions). (click here for latex template of lecture notes.)
to:
were given in the course. click here for lecture notes of the course (this the is first draft of the notes - stay tuned for updated versions, in the mean time click here for errata by Rani Hod). (click here for latex template of lecture notes.)
October 24, 2007, at 09:32 PM
by Boaz Barak -
Changed lines 3-4 from:
Mini-Course: August 23-24 at Princeton University (immediately after RANDOM+APPROX 07).
to:
Mini-Course: August 23-24 at Princeton University (immediately after RANDOM+APPROX 07).
Changed lines 8-9 from:
were given in the course. click here for lecture notes of the course (this the is first draft of the notes - stay tuned for updated versions). (click here for latex template of lecture notes.)
to:
were given in the course. click here for lecture notes of the course (this the is first draft of the notes - stay tuned for updated versions). (click here for latex template of lecture notes.)
Changed lines 13-14 from:
- Szemeredi regularity lemma and Szemeredi's theorem for k=3 / Luca Trevisan
lecture notes
to:
- Szemeredi regularity lemma and Szemeredi's theorem for k=3 / Luca Trevisan lecture notes
Changed lines 16-17 from:
- The sum-product theorem and its applications / Avi Wigderson powerpoint slides
lecture notes
to:
- The sum-product theorem and its applications / Avi Wigderson powerpoint slides lecture notes
Changed lines 19-20 from:
- Proof of the sum-product theorem / Boaz Barak powerpoint slides , (slides with annotations - powerpoint 2007 only)
lecture notes
to:
- Proof of the sum-product theorem / Boaz Barak powerpoint slides , (slides with annotations - powerpoint 2007 only) lecture notes
Changed lines 22-23 from:
- Proof of the regularity lemma (original plan: applications to property testing) / Luca Trevisan
lecture notes
to:
- Proof of the regularity lemma (original plan: applications to property testing) / Luca Trevisan lecture notes
Changed lines 25-26 from:
- Szemeredi's theorem for k=3: Roth's proof / Luca Trevisan
lecture notes
to:
- Szemeredi's theorem for k=3: Roth's proof / Luca Trevisan lecture notes
Changed lines 28-29 from:
- Gowers uniformity norms and sketch of Gowers' proof of Szemeredi's theorem / Luca Trevisan
lecture notes
to:
- Gowers uniformity norms and sketch of Gowers' proof of Szemeredi's theorem / Luca Trevisan lecture notes
Changed lines 31-32 from:
- Applications: Direct Product Theorems / Avi Wigderson
lecture notes
to:
- Applications: Direct Product Theorems / Avi Wigderson lecture notes
Changed lines 34-35 from:
- Applications: PCPs and pseudorandomness / Luca Trevisan
lecture notes
to:
- Applications: PCPs and pseudorandomness / Luca Trevisan lecture notes
Changed lines 37-38 from:
to:
October 24, 2007, at 09:29 PM
by Boaz Barak -
Added line 14:
Added line 18:
Added line 22:
Added line 26:
Added line 30:
Added line 34:
Added line 38:
Added line 42:
October 24, 2007, at 09:25 PM
by Boaz Barak -
Changed lines 8-9 from:
were given in the course. Stay tuned for scribe notes and video recordings of the lectures which should be on this page by mid September 2007. (click here for latex template of lecture notes.)
to:
were given in the course. click here for lecture notes of the course (this the is first draft of the notes - stay tuned for updated versions). (click here for latex template of lecture notes.)
October 24, 2007, at 03:56 PM
by 172.16.29.250 -
Changed line 10 from:
- Introduction and overview / Luca Trevisan
to:
- Introduction and overview / Luca Trevisan
Changed lines 12-13 from:
- Szemeredi regularity lemma and Szemeredi's theorem for k=3 / Luca Trevisan
to:
- Szemeredi regularity lemma and Szemeredi's theorem for k=3 / Luca Trevisan
Changed lines 15-16 from:
- The sum-product theorem and its applications / Avi Wigderson powerpoint slides
to:
- The sum-product theorem and its applications / Avi Wigderson powerpoint slides
Changed line 19 from:
- Proof of the sum-product theorem / Boaz Barak powerpoint slides , (slides with annotations - powerpoint 2007 only)
to:
- Proof of the sum-product theorem / Boaz Barak powerpoint slides , (slides with annotations - powerpoint 2007 only)
Changed line 22 from:
- Proof of the regularity lemma (original plan: applications to property testing) / Luca Trevisan
to:
- Proof of the regularity lemma (original plan: applications to property testing) / Luca Trevisan
Changed line 25 from:
- Szemeredi's theorem for k=3: Roth's proof / Luca Trevisan
to:
- Szemeredi's theorem for k=3: Roth's proof / Luca Trevisan
Changed line 28 from:
- Gowers uniformity norms and sketch of Gowers' proof of Szemeredi's theorem / Luca Trevisan
to:
- Gowers uniformity norms and sketch of Gowers' proof of Szemeredi's theorem / Luca Trevisan
Changed line 31 from:
- Applications: Direct Product Theorems / Avi Wigderson
to:
- Applications: Direct Product Theorems / Avi Wigderson
Changed line 34 from:
- Applications: PCPs and pseudorandomness / Luca Trevisan
to:
- Applications: PCPs and pseudorandomness / Luca Trevisan
October 24, 2007, at 03:55 PM
by 172.16.29.250 -
Deleted line 11:
Deleted line 13:
October 24, 2007, at 03:55 PM
by 172.16.29.250 -
Changed line 13 from:
- Szemeredi regularity lemma and Szemeredi's theorem for k=3 / Luca Trevisan
to:
- Szemeredi regularity lemma and Szemeredi's theorem for k=3 / Luca Trevisan
Changed line 16 from:
- The sum-product theorem and its applications / Avi Wigderson powerpoint slides
to:
- The sum-product theorem and its applications / Avi Wigderson powerpoint slides
Changed line 19 from:
- Proof of the sum-product theorem / Boaz Barak powerpoint slides , (slides with annotations - powerpoint 2007 only)
to:
- Proof of the sum-product theorem / Boaz Barak powerpoint slides , (slides with annotations - powerpoint 2007 only)
Changed line 22 from:
- Proof of the regularity lemma (original plan: applications to property testing) / Luca Trevisan
to:
- Proof of the regularity lemma (original plan: applications to property testing) / Luca Trevisan
Changed line 25 from:
- Szemeredi's theorem for k=3: Roth's proof / Luca Trevisan
to:
- Szemeredi's theorem for k=3: Roth's proof / Luca Trevisan
Changed line 28 from:
- Gowers uniformity norms and sketch of Gowers' proof of Szemeredi's theorem / Luca Trevisan
to:
- Gowers uniformity norms and sketch of Gowers' proof of Szemeredi's theorem / Luca Trevisan
Changed line 31 from:
- Applications: Direct Product Theorems / Avi Wigderson
to:
- Applications: Direct Product Theorems / Avi Wigderson
Changed line 34 from:
- Applications: PCPs and pseudorandomness / Luca Trevisan
to:
- Applications: PCPs and pseudorandomness / Luca Trevisan
October 24, 2007, at 03:53 PM
by 172.16.29.250 -
Changed line 10 from:
- 'Introduction and overview' / Luca Trevisan
to:
- Introduction and overview / Luca Trevisan
October 24, 2007, at 03:53 PM
by 172.16.29.250 -
Changed line 10 from:
- Introduction and overview / Luca Trevisan
to:
- 'Introduction and overview' / Luca Trevisan
Changed line 13 from:
- Szemeredi regularity lemma and Szemeredi's theorem for k=3 / Luca Trevisan
to:
- Szemeredi regularity lemma and Szemeredi's theorem for k=3 / Luca Trevisan
Changed line 16 from:
- The sum-product theorem and its applications / Avi Wigderson powerpoint slides
to:
- The sum-product theorem and its applications / Avi Wigderson powerpoint slides
Changed line 19 from:
- Proof of the sum-product theorem / Boaz Barak powerpoint slides , (slides with annotations - powerpoint 2007 only)
to:
- Proof of the sum-product theorem / Boaz Barak powerpoint slides , (slides with annotations - powerpoint 2007 only)
Changed line 22 from:
- Proof of the regularity lemma (original plan: applications to property testing) / Luca Trevisan
to:
- Proof of the regularity lemma (original plan: applications to property testing) / Luca Trevisan
Changed line 25 from:
- Szemeredi's theorem for k=3: Roth's proof / Luca Trevisan
to:
- Szemeredi's theorem for k=3: Roth's proof / Luca Trevisan
Changed line 28 from:
- Gowers uniformity norms and sketch of Gowers' proof of Szemeredi's theorem / Luca Trevisan
to:
- Gowers uniformity norms and sketch of Gowers' proof of Szemeredi's theorem / Luca Trevisan
Changed line 31 from:
- Applications: Direct Product Theorems / Avi Wigderson
to:
- Applications: Direct Product Theorems / Avi Wigderson
Changed line 34 from:
- Applications: PCPs and pseudorandomness / Luca Trevisan
to:
- Applications: PCPs and pseudorandomness / Luca Trevisan
October 24, 2007, at 03:51 PM
by 172.16.29.250 -
Changed lines 14-15 from:
to:
Video (Real media: low res, high res)
Changed lines 17-18 from:
to:
Video (Real media: low res, high res)
Changed lines 20-21 from:
to:
Video (Real media: low res, high res)
Changed lines 23-24 from:
to:
Video (Real media: low res, high res)
Changed lines 26-27 from:
to:
Video (Real media: low res, high res)
Changed lines 29-30 from:
to:
Video (Real media: low res, high res)
Changed lines 32-33 from:
to:
Video (Real media: low res, high res)
Changed lines 35-36 from:
to:
Video (Real media: low res, high res)
October 24, 2007, at 03:45 PM
by 172.16.29.250 -
Changed lines 11-13 from:
Video (Real media:
low res, high res)
to:
Video (Real media: low res, high res)
October 24, 2007, at 03:44 PM
by 172.16.29.250 -
Changed lines 12-14 from:
to:
October 24, 2007, at 03:44 PM
by 172.16.29.250 -
Changed lines 10-12 from:
- Introduction and overview / Luca Trevisan
Video (
to:
- Introduction and overview / Luca Trevisan
Video (Real media:
October 24, 2007, at 03:42 PM
by 172.16.29.250 -
Added lines 12-15:
Video (
low res,
high res)
August 28, 2007, at 03:21 PM
by Boaz Barak -
Changed lines 10-28 from:
- Introduction and overview / Luca Trevisan
- Szemeredi regularity lemma and Szemeredi's theorem for k=3 / Luca Trevisan
- The sum-product theorem and its applications / Avi Wigderson powerpoint slides
- Proof of the sum-product theorem / Boaz Barak powerpoint slides , (slides with annotations - powerpoint 2007 only)
- Proof of the regularity lemma (original plan: applications to property testing) / Luca Trevisan
- Szemeredi's theorem for k=3: Roth's proof / Luca Trevisan
- Gowers uniformity norms and sketch of Gowers' proof of Szemeredi's theorem / Luca Trevisan
- Applications: Direct Product Theorems / Avi Wigderson
- Applications: PCPs and pseudorandomness / Luca Trevisan
to:
- Introduction and overview / Luca Trevisan
- Szemeredi regularity lemma and Szemeredi's theorem for k=3 / Luca Trevisan
- The sum-product theorem and its applications / Avi Wigderson powerpoint slides
- Proof of the sum-product theorem / Boaz Barak powerpoint slides , (slides with annotations - powerpoint 2007 only)
- Proof of the regularity lemma (original plan: applications to property testing) / Luca Trevisan
- Szemeredi's theorem for k=3: Roth's proof / Luca Trevisan
- Gowers uniformity norms and sketch of Gowers' proof of Szemeredi's theorem / Luca Trevisan
- Applications: Direct Product Theorems / Avi Wigderson
- Applications: PCPs and pseudorandomness / Luca Trevisan
August 28, 2007, at 03:14 PM
by Boaz Barak -
Changed lines 16-19 from:
- Proof of the sum-product theorem / Boaz Barak powerpoint slides ,
(slides with annotations - powerpoint 2007 only)
to:
- Proof of the sum-product theorem / Boaz Barak powerpoint slides , (slides with annotations - powerpoint 2007 only)
August 28, 2007, at 03:13 PM
by Boaz Barak -
Changed lines 17-19 from:
'-(slides with annotations - powerpoint 2007 only)
-'
to:
(slides with annotations - powerpoint 2007 only)
August 28, 2007, at 03:13 PM
by Boaz Barak -
Changed lines 16-17 from:
- Proof of the sum-product theorem / Boaz Barak powerpoint slides
to:
- Proof of the sum-product theorem / Boaz Barak powerpoint slides ,
'-(slides with annotations - powerpoint 2007 only)
-'
August 28, 2007, at 02:56 PM
by Boaz Barak -
Changed lines 14-19 from:
- The sum-product theorem and its applications / Avi Wigderson
- Proof of the sum-product theorem / Boaz Barak powerpoint slides Δ
- Proof of the regularity lemma / Luca Trevisan
to:
- The sum-product theorem and its applications / Avi Wigderson powerpoint slides
- Proof of the sum-product theorem / Boaz Barak powerpoint slides
- Proof of the regularity lemma (original plan: applications to property testing) / Luca Trevisan
August 26, 2007, at 09:23 PM
by Boaz Barak -
Changed lines 7-25 from:
Registration: Registration to the mini-course is FREE but you need to register by August 1st, 2007. CLICK HERE FOR REGISTRATION WEB PAGE. Registration deadline is now over! you can still register for a waiting list but we can not guarantee a place in the course anymore.
Program: click here for course program
Local information: Course will be held in Princeton university.
We have a block of rooms reserved at the Nassau Inn
under the name "Additive Combinatorics Mini-Course". The room rate is $129 + tax. Reservations must be made
by calling the Nassau Inn at 1-800-862-7728 or 609-921-7500 (you will need
a credit card to hold the reservation).
The cutoff date for reservations is July 23.
You will need a picture ID when you check in.
See the RANDOM+APPROX 07 page for information on transportation etc.
Parking: use LOT 21 or the meters outside the CS department (bring change) - see
this map. You need to put in your dashboard the following permit.
to:
Program: The following lectures
were given in the course. Stay tuned for scribe notes and video recordings of the lectures which should be on this page by mid September 2007. (click here for latex template of lecture notes.)
- Introduction and overview / Luca Trevisan
- Szemeredi regularity lemma and Szemeredi's theorem for k=3 / Luca Trevisan
- The sum-product theorem and its applications / Avi Wigderson
- Proof of the sum-product theorem / Boaz Barak powerpoint slides Δ
- Proof of the regularity lemma / Luca Trevisan
- Szemeredi's theorem for k=3: Roth's proof / Luca Trevisan
- Gowers uniformity norms and sketch of Gowers' proof of Szemeredi's theorem / Luca Trevisan
- Applications: Direct Product Theorems / Avi Wigderson
- Applications: PCPs and pseudorandomness / Luca Trevisan
click here for PDF program and schedule
August 13, 2007, at 11:58 AM
by Boaz Barak -
Changed lines 9-11 from:
Program: To be announced. Lectures will take place between 9am to 5pm on August 23rd and 24th.
to:
August 06, 2007, at 01:21 PM
by Boaz Barak -
Added lines 23-25:
Parking: use LOT 21 or the meters outside the CS department (bring change) - see
this map. You need to put in your dashboard the following permit.
August 01, 2007, at 09:13 PM
by Boaz Barak -
Changed lines 7-8 from:
Registration: Registration to the mini-course is FREE but you need to register by August 1st, 2007. CLICK HERE FOR REGISTRATION WEB PAGE.
to:
Registration: Registration to the mini-course is FREE but you need to register by August 1st, 2007. CLICK HERE FOR REGISTRATION WEB PAGE. Registration deadline is now over! you can still register for a waiting list but we can not guarantee a place in the course anymore.
Added line 44:
- Structure and Randomness in combinatorics - FOCS 07 tutorial by Terence Tao
June 07, 2007, at 07:57 PM
by 172.16.29.250 -
Changed lines 19-21 from:
See RANDOM+APPROX 07 page for information on transportation etc.
to:
You will need a picture ID when you check in.
See the RANDOM+APPROX 07 page for information on transportation etc.
June 07, 2007, at 01:49 PM
by 172.16.29.250 -
Changed lines 12-14 from:
Local information: Course will be held in Princeton university. See RANDOM+APPROX 07 page for information on hotels, transportation etc..
to:
Local information: Course will be held in Princeton university.
We have a block of rooms reserved at the Nassau Inn
under the name "Additive Combinatorics Mini-Course". The room rate is $129 + tax. Reservations must be made
by calling the Nassau Inn at 1-800-862-7728 or 609-921-7500 (you will need
a credit card to hold the reservation).
The cutoff date for reservations is July 23.
See RANDOM+APPROX 07 page for information on transportation etc.
June 03, 2007, at 11:17 AM
by Boaz -
Deleted lines 2-3:
Changed lines 27-29 from:
Organizers: Boaz Barak and Moses Charikar. Email: acminicourse@gmail.com
to:
Organizers: Boaz Barak and Moses Charikar. Email: acminicourse@gmail.com
June 03, 2007, at 11:16 AM
by Boaz -
Changed lines 11-14 from:
Programs: To be announced. Lectures will take place between 9am to 5pm on August 23rd and 24th.
to:
Program: To be announced. Lectures will take place between 9am to 5pm on August 23rd and 24th.
Local information: Course will be held in Princeton university. See RANDOM+APPROX 07 page for information on hotels, transportation etc..
June 03, 2007, at 11:14 AM
by Boaz -
Changed lines 9-10 from:
Registration: Registration to the mini-course is FREE but you need to register by August 1st, 2007. CLICK HERE FOR REGISTRATION WEB PAGE.
to:
Registration: Registration to the mini-course is FREE but you need to register by August 1st, 2007. CLICK HERE FOR REGISTRATION WEB PAGE.
June 03, 2007, at 10:10 AM
by Boaz -
Added lines 3-4:
Changed lines 13-14 from:
Questions/comments/requests: Email acminicourse@gmail.com
to:
June 03, 2007, at 10:09 AM
by Boaz -
Added lines 11-12:
Questions/comments/requests: Email acminicourse@gmail.com
Changed lines 25-27 from:
Organizers: Boaz Barak and Moses Charikar
to:
Organizers: Boaz Barak and Moses Charikar. Email: acminicourse@gmail.com
June 03, 2007, at 01:25 AM
by Boaz -
Changed lines 7-8 from:
Registration: Registration to the mini-course is FREE but you need to register by August 1st, 2007. Click here to register.
to:
Registration: Registration to the mini-course is FREE but you need to register by August 1st, 2007. CLICK HERE FOR REGISTRATION WEB PAGE.
June 03, 2007, at 01:25 AM
by Boaz -
Changed lines 5-9 from:
Lecturers: Luca Trevisan and Avi Wigderson
Registration: Registration to the mini-course is FREE but you need to register by August 1st, 2007. Registration web page will be reachable through this site by June 8th, 2007.
to:
Lecturers: Boaz Barak, Luca Trevisan and Avi Wigderson
Registration: Registration to the mini-course is FREE but you need to register by August 1st, 2007. Click here to register.
Programs: To be announced. Lectures will take place between 9am to 5pm on August 23rd and 24th.
Changed lines 13-14 from:
Additive combinatorics studies structural properties of subsets of numbers and other Abelian groups. It is concerned with questions such as what conditions on a set A assure that A contains long arithmetic progressions, or what conditions imply that A's sum-set (the set {x+y: x,y in A}) is small or large . Recent years saw both important advances in this field and some computer science applications. This mini course will review both of these from the perspective of theoretical computer science.
to:
Additive combinatorics studies structural properties of subsets of numbers and other Abelian groups. It is concerned with questions such as what conditions on a set A assure that A contains long arithmetic progressions, or what conditions imply that A's sum-set (the set {x+y: x,y in A}) is small or large . Recent years saw both important advances in this field and some computer science applications. This mini course will review both of these from the perspective of theoretical computer science. The course is intended for researchers and students with background in theoretical computer science, but no prior knowledge of additive combinatorics.
May 31, 2007, at 09:38 PM
by Boaz -
Added lines 1-30:
Additive Combinatorics and Computer Science.
Mini-Course: August 23-24 at Princeton University (immediately after RANDOM+APPROX 07).
Lecturers: Luca Trevisan and Avi Wigderson
Registration: Registration to the mini-course is FREE but you need to register by August 1st, 2007. Registration web page will be reachable through this site by June 8th, 2007.
Synopsis:
Additive combinatorics studies structural properties of subsets of numbers and other Abelian groups. It is concerned with questions such as what conditions on a set A assure that A contains long arithmetic progressions, or what conditions imply that A's sum-set (the set {x+y: x,y in A}) is small or large . Recent years saw both important advances in this field and some computer science applications. This mini course will review both of these from the perspective of theoretical computer science.
Topics will include:
- Proof of Szemeredi's Theorem on existence of long arithmetic progression in every sufficiently dense set.
- Gowers uniformity - a higher degree variant of Fourier analysis.
- Proof of the Bourgain-Katz-Tao finite-field sum product theorem.
- Applications to property testing and PCP's.
- Applications to the constructions of randomness extractors.
Organizers: Boaz Barak and Moses Charikar
Links:
- Additive Combinatorics - book by Terence Tao and Van Vu
- Lecture notes on additive combinatorics: Tao Vu Green Gowers
|
|
|