Flajolet Lecture Prize
{{Short description|Scientific prize and lecture series}}
The Philippe Flajolet Lecture Prize is awarded to for contributions to analytic combinatorics and analysis of algorithms, in the fields of theoretical computer science. This prize is named in memory of Philippe Flajolet.
History
The Flajolet Lecture Prize has been awarded since 2014. The Flajolet Lecture Prize is awarded in odd-numbered years. After being selected for the prize, the recipient delivers the Flajolet Lecture during the following year. This lecture is organized as a keynote address at the International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA).{{cite web | url = https://aofa.cs.purdue.edu/ | title = Analysis of Algorithms | access-date = 20 March 2021}} AofA is the international conference that began as a series of seminars, started by Flajolet and others in 1993. The Selection Committee consists of three members from this field.
Scientific topics
The recipients of the Flajolet Lecture Prize work in a variety of areas, including
maps,
In the inaugural lecture, Don Knuth discussed five "Problems That Philippe Would Have Loved".{{Cite web|url=https://www-cs-faculty.stanford.edu/~knuth/flaj2014.pdf|title=Problems That Philippe Would Have Loved|author=Donald Knuth|publisher=Stanford University|access-date = 23 March 2022}} Knuth surveyed five problems, including enumeration of polyominoes, mathematical tiling, tree pruning, lattice paths, and perturbation theory. In particular, he discussed the asymptotic enumeration of polyominoes (see OEIS entry A001168{{Cite web|url=https://oeis.org/A001168|title=Number of fixed polyominoes with n cells|author=N. J. A. Sloane|publisher = On-Line Encyclopedia of Integer Sequences|access-date = 23 March 2022}} for context and history). Knuth's discussion of forest pruning caused Peter Luschny to observe a connection to Dyck paths (see OEIS entry A091866{{Cite web|url=https://oeis.org/A091866|title=Number of Dyck paths of semilength n having pyramid weight k|author=Emeric Deutsch|publisher = On-Line Encyclopedia of Integer Sequences|access-date = 23 March 2022}}). The portion of the talk on Lattice Paths of Slope 2/5 focused on a theorem by Nakamigawa and Tokushige.{{cite journal |last1= Nakamigawa|first1= Tomoki|last2= Tokushige|first2= Norihide|date= 2012|title= Counting Lattice Paths via a New Cycle Lemma|url= https://epubs.siam.org/doi/abs/10.1137/100796431|journal= SIAM Journal on Discrete Mathematics|volume= 26|issue= 2|pages= 745–754|doi= 10.1137/100796431|publisher= Society for Industrial and Applied Mathematics|access-date=23 March 2022|citeseerx= 10.1.1.220.6893}}{{Cite web|url=https://oeis.org/A322631|title=a(n) = 2*binomial(7*n-1,2*n)/(7*n-1)|author=Hugo Pfoertner|publisher = On-Line Encyclopedia of Integer Sequences|access-date = 23 March 2022}} Knuth made a conjecture about the related enumeration of lattice paths, which was subsequently resolved by Cyril Banderier and Michael Wallner.{{Cite book|last1= Banderier|first1= Cyril|last2= Wallner|first2= Michael|title=2015 Proceedings of the Twelfth Workshop on Analytic Algorithmics and Combinatorics (ANALCO)|chapter= Lattice paths of slope 2/5|year= 2015|pages= 105–113|doi= 10.1137/1.9781611973761.10|arxiv= 1605.02967|isbn= 978-1-61197-376-1|s2cid= 15496496}}{{Cite web|url=https://meetings.siam.org/sess/dsp_talk.cfm?p=69578|title=Lattice paths of slope 2/5|last1= Banderier|first1= Cyril|last2= Wallner|first2= Michael|publisher = Society for Industrial and Applied Mathematics, Meeting on Analytic Algorithmics and Combinatorics|date = 2015|access-date = 23 March 2022}}{{cite book |last1= Banderier|first1= Cyril|last2= Wallner|first2= Michael|date= 2019|chapter= The Kernel Method for Lattice Paths Below a Line of Rational Slope|url = https://link.springer.com/book/10.1007/978-3-030-11102-1|chapter-url = https://link.springer.com/chapter/10.1007/978-3-030-11102-1_7|title= Lattice Path Combinatorics and Applications|series= Developments in Mathematics|volume= 58|pages= 119–154|doi= 10.1007/978-3-030-11102-1|editor-last1= Andrews|editor-first1=George|editor-last2=Krattenthaler|editor-first2=Christian|editor-last3=Krinik|editor-first3=Alan|publisher= Springer|isbn= 978-3-030-11101-4|s2cid= 197480284|access-date=23 March 2022}} Knuth's discussion of lattice paths also led to the creation of two new OEIS entries, A322632{{Cite web|url=https://oeis.org/A322632|title=Decimal expansion of the real solution to 23*x^5 - 41*x^4 + 10*x^3 - 6*x^2 - x - 1 = 0|author=Hugo Pfoertner|publisher = On-Line Encyclopedia of Integer Sequences|access-date = 23 March 2022}} and A322633.{{Cite web|url=https://oeis.org/A322633|title=Decimal expansion of the real solution to 11571875*x^5 - 5363750*x^4 + 628250*x^3 - 97580*x^2 + 5180*x - 142 = 0, multiplied by 3/7|author=Hugo Pfoertner|publisher = On-Line Encyclopedia of Integer Sequences|access-date = 23 March 2022}}
The 2016 lecture by Robert Sedgewick focused on a topic dating back to one of Flajolet's earliest papers, on approximate counting methods for streaming data. The talk drew connections between "practical computing" and theoretical computer science. As a key example of these connections, Sedgewick emphasized the way that Flajolet revisited the topic of approximate counting repeatedly during his career, starting with the Flajolet–Martin algorithm for probabilistic counting{{cite journal |last1= Flajolet|first1= Philippe|last2= Nigel Martin|first2= G.|date= 1985|title= Probabilistic counting algorithms for data base applications|journal= Journal of Computer and System Sciences|volume= 31|issue= 2|pages= 182–209|doi= 10.1016/0022-0000(85)90041-8|doi-access= free|url= https://hal.inria.fr/inria-00076244/file/RR-0313.pdf}} and leading the introduction of methods for Loglog Counting{{Cite book |doi=10.1007/978-3-540-39658-1_55 |chapter=Loglog Counting of Large Cardinalities |chapter-url=http://algo.inria.fr/flajolet/Publications/DuFl03-LNCS.pdf |access-date=23 March 2022 |title= Algorithms - ESA 2003 |volume=2832 |pages=605 |series=Lecture Notes in Computer Science |year=2003 |last1=Durand |first1=Marianne |last2=Flajolet |first2=Philippe |isbn=978-3-540-20064-2}} and HyperLogLog counting.{{cite journal |last1=Flajolet |first1=Philippe |last2=Fusy |first2=Éric |last3=Gandouet |first3=Olivier |last4=Meunier |first4=Frédéric |title=Hyperloglog: The analysis of a near-optimal cardinality estimation algorithm |url=https://dmtcs.episciences.org/3545 |access-date=23 March 2022 |year=2007 |volume=AH |pages=137–156 |journal=Discrete Mathematics and Theoretical Computer Science Proceedings |location=Nancy, France}} Sedgewick's talk emphasized not only the underlying theory but also the experimental validation of approximate counting, and its modern applications in cloud computing. He also introduced an algorithm called HyperBitBit, which is appropriate in applications which involve small-scale, frequent calculations.
Recipients
See also
Notes
{{notelist|group=lower-alpha}}
References
{{reflist}}
External links
- [https://aofa.cs.purdue.edu/ Analysis of Algorithms international community website]
Category:Theoretical computer science
Category:Computer science awards
Category:Science lecture series
Category:Recurring events established in 2014