• Home
• M.Sc. thesis
• Talks and lecture notes
• Links

Talks

I am currently finishing my MS studies in St. Petersburg, Russia, so all my lecture notes below are in Russian.

Fall 2011	A Bound on the Betti Numbers of Semialgebraic Sets Defined over Quadratic Maps
	Ben-Or's bound on decision tree complexity of semialgebraic sets: ben-or.pdf + betti-bound.pdf
	Algebraic Complexity Theory: overview and models of computation: act.pdf
Spring 2011	What is Alexander polynomial? (a very expository talk): ...
	Definitions of the Reidemeister torsion and the Whitehead torsion (Turaev's book)
	Handout on the torsion of an acyclic complex (Turaev's book): torsion-ho.pdf
	A bound on Betti numbers of real algebraic sets (Milnor–Thom bound): betti-bound.pdf
	Basic applications of model theory in algebraic and real algebraic geometry: acf.pdf | rcf.pdf
	Computing the main structural blocks of algebras. The Jacobson radical (based on the survey by Ivanyos & Rónyai): slides
Fall 2010	Handout for a talk on Kolmogorov complexities: smpr.pdf
	An introduction to the cylindrical algebraic decomposition (incomplete notes): PDF
Spring 2010	The computational complexity of knot and link problems: abstract | slides
	Two introductory talks about the Coq proof assistant (based on Coq’Art): coq0.pdf | coq1.pdf

---

Lecture notes

Category Theory (PDMI, Fall 2011, Prof. Nikolai Vavilov)

My lecture notes: http://cadadr.org/notes/categories.pdf (updated weekly).

• Categories^{[nLab, WP]}
• Functors^{[nLab, WP]}
• Representable functors^{[nLab, WP]}
• Monomorphisms^{[nLab, WP]}, epimorphisms^{[nLab, WP]}; (co)retractions^[WP]
• Products of categories^[WP]
• Initial and terminal objects^{[nLab-1, nLab-2, WP]}
• Products^{[nLab, WP]} and coproducts^{[nLab, WP]}
• Pullbacks^{[nLab, WP]} and pushouts^{[nLab, WP]}
• Limits and colimits^{[nLab-1, nLab-2, WP]}
• Natural transformations^{[nLab, WP]}
• 2-categories^{[nLab, WP]}
• Yoneda lemma^{[nLab, WP]}
• Adjoint functors^{[nLab, WP]}
• Equivalence of categories^{[nLab, WP]}
• Generators and cogenerators^{[nLab-1, nLab-2, WP]}
• Abelian categories^{[nLab, WP]}
• Toposes^{[nLab, WP]}
• Sheaves^{[nLab, WP]}

Algebraic Complexity Theory (U RAS, Fall 2011, Prof. Dmitry Itsykson)

My notes from the seminar:

1. http://cadadr.org/notes/complexity/act.pdf
   • Straight-line programs
   • Complexity measures
   • The dimension lower bound
   • Autarky of a field extension
2. http://cadadr.org/notes/rag/ben-or.pdf
   • The Milnor–Thom bound on the sum of Betti numbers of a real algebraic set
   • Ben-Or's bound on decision tree complexity of semialgebraic sets
   • Some applications of Ben-Or's bound

Rational points on transcendental curves and varieties (Summer School "Algebra and Geometry", Yaroslavl, 2011, Prof. Yuri Bilu)

Unofficial lecture notes, written by myself: http://cadadr.org/notes/yaroslavl/bilu.pdf

• The theorem of Bombieri and Pila
• Counting rational points
• Multi-dimensional theorem of Bombieri and Pila
• Manin–Mumford conjecture
• Elliptic curves
• André–Oort conjecture

Noncommutative Rings (PDMI, Fall 2011, Prof. Nikolai Vavilov)

Some lecture notes prepared by me and other students: noncommutative.pdf

Outline:

• Density theorem: let R be a primitive ring and M be a faithful simple R-module. Then for each f ∈ End (_RM) and each finite set of elements u₁, …, u_n there exists r ∈ R such that r u_i = f (u_i).
• Jacobson–Herstein theorem: if for all x,y there exists N(x,y) > 1 such that [x,y]^N(x,y) = [x,y], then the ring is commutative.
• Constructions of division algebras: Hilbert's twist and K((t;σ)); cyclic algebras (K/F,σ,ε).
• The Brauer group of a field Br(K).
• Symbol algebras (α,β)_n, Steinberg symbols {α,β}, and the Merkurjev–Suslin theorem: K₂(F)/n K₂(F) is isomorphic to Br(F)_n.
• PI-rings: Amitsur–Levitzki theorem, central polynomials, Kaplansky's theorem.

Homology Theory (PDMI, Spring 2011, Prof. Semyon Podkorytov)

Unofficial lecture notes, written by myself.

To be written. Here is a rough working draft: http://cadadr.org/tmp/homology-0.pdf

A brief outline:

• Singular and simplicial homology
• H₁(X) = π₁(X)^ab
• Homotopic maps induce the same morphism in H_•
• Barycentric subdivision
• Covering theorem
• Mayer–Vietoris exact sequence
• Euler characteristic
• Homology with coefficients in arbitrary abelian group
• Lefschetz fixed point theorem
• Relative homology
• Excision theorem
• Degree of a map Sⁿ → Sⁿ
• Cellular homology. Application: H_•(RPⁿ) and H_•(CPⁿ)
• Universal coefficient theorem
• Künneth theorem
• Acyclic models theorem
• Eilenberg–Zilber theorem
• Exterior homological product
• Cohomology
• Universal coefficient theorem for cohomology
• Bruschlinsky group: [X;S¹] ≅ H¹(X;Z)
• Alexander–Whitney map
• Exterior cohomological product
• Künneth theorem for cohomology
• Cup-product
• Poincaré duality
• Signature of a 4k-manifold
• Euler class of an oriented vector bundle

Useful materials:

• Algebraic Topology by Allen Hatcher: http://www.math.cornell.edu/~hatcher/AT/ATpage.html
• Elements of Homology Theory by Victor Prasolov [in Russian]: http://www.mccme.ru/prasolov/
• Tor & Ext: http://www.math.uchicago.edu/~may/MISC/TorExt.pdf
• A survey of cohomology theories: http://people.maths.ox.ac.uk/~tillmann/coho.pdf
• Introduction to Homology Theory by M. E. Kazaryan [in Russian]: http://www.mi.ras.ru/~kazarian/papers/homology05.pdf

Logic and Model Theory (U RAS, Fall 2010/Spring 2011, Prof. Sergey Nikolenko)

Official lecture notes, written by myself:

• Basic notions of model theory: model-theory-intro.pdf
• Ehrenfeucht–Fraïssé games: ehrenfeucht-fraisse.pdf
• [My Talk] Basic applications of model theory in algebraic geometry: acf.pdf
• [My Talk] Basic applications of model theory in real algebraic geometry: rcf.pdf

Useful materials:

• Model theory: an Introduction by David Marker
• Lecture notes by Anand Pillay
• A Problem Course in Mathematical Logic by Stefan Bilaniuk

Computational Complexity (U RAS, Fall 2010, Prof. Dmitry Itsykson)

Unofficial lecture notes, written by myself:

• PDF: complexity-1.pdf
• LaTeX: complexity-1.tar.gz
• Some notes for Computational Complexity II: cc2.pdf

I still plan to fill the gaps.

A brief outline:

• Turing machines
• P vs. NP
• Karp reductions, Cook reductions
• NP-completeness
• Ladner's theorem (NP-intermediate)
• Baker–Gill–Solovay: relativization of P vs. NP
• Time hierarchy
• Space hierarchy, PSPACE, NL
• Polynomial hierarchy
• Circuit complexity, P/poly, NC
• Randomized computation, BPP, RP, co-RP, Sipser–Gács–Lautemann
• Interactive Proof Systems, IP = PSPACE
• Arthur–Merlin protocols, Goldwasser–Sipser: IP[k(n)] ⊆ AM[k(n)+2]
• Counting classes: #P, ⊕P, and PP
• Valiant–Vazirani
• #P-completeness of 0-1 PERMANENT
• Introduction to probabilistically checkable proofs

Useful materials:

• Computational Complexity: A Modern Approach by Sanjeev Arora and Boaz Barak
• The Complexity Zoo
• Lecture notes for a course by Luca Trevisan
• Lecture notes for a course by Oded Goldreich
• Lecture notes for a course by prof. Edward Hirsch

Proof Complexity (PDMI, Fall 2010, Prof. Edward Hirsch)

Official videos and lecture notes, written by me and classmates:

• Lecture 1. Basic definitions and examples: Video | PDF
• Lecture 2. Frege systems: Video | PDF
• Lecture 3. CP in Frege; optimal proof systems: Video | PDF
• Lecture 4. Disjoint NP-pairs: Video | PDF
• Lecture 5. Lower bounds on CP; a lower bound for Tseitin's formulas in Res: Video | PDF
• Lecture 6. Lower bounds for PHP and Res correctness: Video | PDF (draft)
• Lecture 7. An overview of algebraic and semialgebraic proof systems: Video [there is no TeX'ed transcript]
• Lecture 8. Beame–Pitassi–Segerlind: Lower bounds for LS from communication complexity: Video | PDF (draft)

Miscellaneous

Here are some useful links from the past courses.

Toric Varieties

Lectures by Gaiane Panina: http://cadadr.org/notes/toric/panina-toric.pdf

Bounded Arithmetic

Books and surveys on bounded arithmetic:

• Samuel R. Buss, Handbook of Proof Theory, Chapter II
• Jan Krajíček, Bounded arithmetic, propositional logic, and complexity theory
• Stephen A. Cook and Phuong Nguyen, Logical Foundations of Proof Complexity

Kolmogorov Complexity

A comprehensive book Kolmogorov Complexity and Algorithmic Randomness by Vladimir Uspensky, Nikolai Vereschagin, and Alexander Shen:

• ftp://ftp.mccme.ru/users/shen/kolmbook.pdf [in Russian]

It was used as the main source for a seminar on Kolmogorov complexity in Fall 2010 (chaired by Prof. Dmitry Itsykson).

Discrete Mathematics

Some sources for a course on advanced topics in discrete mathematics taught by Prof. Dmitry Itsykson in Spring 2011:

• Expander graphs and their applications by Shlomo Hoory, Nathan Linial, and Avi Wigderson
• Extremal Combinatorics by Stasys Jukna
• The Probabilistic Method by Noga Alon and Joel Spencer
• Spectra of graphs by Andries E. Brouwer and Willem H. Haemers
• Algorithmic Introduction to Coding Theory by Madhu Sudan
• Lecture notes on expander graphs and their applications by Andrei Romashchenko [in Russian]
• Notes on coding theory by Andrei Romashchenko, Andrei Rumyantsev, and Alexander Shen [in Russian]
• A different exposition of codes can be found in Using Algebraic Geometry by David A. Cox, John B. Little, and Don O'Shea (chapters 9 and 10)

The Graph Isomorphism Problem

Lecture notes on the graph isomorphism problem (Fall 2010; Prof. I. N. Ponomarenko)