- Module 1: Introduction and Classical Cryptography, Perfect Secrecy, One Time Pad.
- Module 2: Symmetric Key Encryption. Computational Security, Concrete vs Asymptotic Approach. Semantic Security. Pseudorandom generators and Stream ciphers, Pseudorandom Functions and Block Ciphers. Practical Constructions.
- Module 3: Hash Functions and Message Authentication Codes. Notions of Security, Generic Attacks, Domain Extension techniques, CBC MAC, HMAC, PMAC, Idea of Authenticated Encryption.
- Module 4: Review of Basic Number Theory. Hardness Assumptions. One-way functions, Trapdoor Permutations, RSA assumptions, Discrete Log and Diffie Hellman Assumptions, SIS and LWE Assumptions. Introduction to Elliptic Curves (Optional)
- Module 5. Key Exchange Protocols and Key Management.
- Module 6. Public Key Encryption, Semantic Security, El Gamal Encryption, Padded RSA PKCS\#1 v1.5. Random Oracle Technique, OAEP.
- Module 7. Digital Signatures, Hash and Sign paradigm, Schnorr Signature, Forking Lemma, DSA. SSL/TLS.
- Module 8. (Optional) Idea of some of the following notions, Protocols and Zero Knowledge Proofs, Multiparty Computations and Oblivious Transfers, Secret Sharing. Algorithms for factoring and computing discrete logarithms, Linear and Differential Cryptanalysis, Crypto Currencies.
UG Elective Courses
Course No
CS451
Prerequisites
CS202, CS301
Credit
4
Classes per week
3 Lectures + 1 Tutorial
Syllabus
Reference Books
- J. Katz and Y. Lindell, Introduction to Modern Cryptography. CRC, 2014.
Course No
CS452
Prerequisites
CS202
Credit
4
Classes per week
3 Lectures + 1 Tutorial
Syllabus
- Module 1: Entropy, Characterization and Properties. Application to Combinatorics. Mutual Information and KL Divergence.
- Module 2: Source coding theorem, lossless compression of data, Lempel-Ziv Algorithm, Optimal lossless coding.
- Module 3: Communication channels (binary symmetric, erasure) and channel capacity, channel coding theorem.
- Module 3: Introduction to Error Correcting Codes. Hamming Codes and Hamming Bounds. BCH Codes, Maximum likelihood decoding and syndrome decoding; coding theory bounds.
- Module 4: Reed-Solomon codes and the Berlekamp-Welch decoding algorithm with Analysis, List Decoding of Reed-Solomon Codes.
- Module 5: Reed-Muller Code and Local decoding.
- Module 6: (Optional) Lovasz Local lemma and proof.
Reference Books
- T. M. Cover and J. A. Thomas, ``Elements of Information Theory'' (Second Edition, Wiley).
- S. Ling C. Xing, `` Coding Theory: A First Course'', Cambridge University Press.
- J. Radhakrishnan, ``Entropy and Counting'', http://www.tcs.tifr.res.in/~jaikumar/Papers/EntropyAndCounting.pdf
- V. Guruswami, A. Rudra and M. Sudan, ``Essential Coding Theory (Draft of a new book)'', available at http://www.cse.buffalo.edu/faculty/atri/courses/coding-theory/book/
- F.J. MacWilliams and N.J.A. Sloane, The Theory of Error-Correcting Codes, North-Holland ML, 1983.
Course No
CS453
Prerequisites
CS201, CS202, CS301
Credit
4
Classes per week
3 Lectures + 1 Tutorial
Syllabus
- Module 1: Introduction, P and NP - Review of Turing machines, universal Turing machines, and uncomputable functions, P vs. NP, NP vs. co-NP, and NP-completeness, EXP, NEXP
- Module 2: Cook Levin's Theorem
- Module 3: Diagonalization, Space complexity (Savitch's Theorem, Immerman-Szelepchenyi Theorem, and Reyngold's Theorem.), Polynomial Hierarchy
- Module 4: Interactive Proofs - PCP theorem and its application to approximability, Queery Complexity, Communication Complexity
- Module 5: Circuit complexity and lower bounds
- Module 6: Hardness vs. Randomness - Randomized Computation, derandomization, Pseudo-random generators
- Module 7: Polynomial identity testing vs Lower bounds for arithmetic circuits
Reference Books
- S. Arora and B. Barak, ``Computational Complexity: A Modern Approach'', Cambridge University Press.
- O. Goldreich, ``Computational Complexity: A conceptual perspective'', Cambridge University Press.
- C. H. Papadimitriou, Computational Complexity, Pearson Education.
- J. Hopcroft, R. Motwani, J. D. Ullman. Introduction to Automata Theory, Languages, and Computation. Pearson Education.
Course No
CS454
Prerequisites
CS202, CS301
Credit
4
Classes per week
3 Lectures + 1 Tutorial
Syllabus
- Module 1: Basic geoemetry and linear algebra related to Linear Programming. Simplex-method and Duality theorem (leading to Von Neumann's minmax principle) and complementary slackness.
- Module 2: Ellipsoid algorithm. separation oracles.
- Module 3:Semidefinite programming as an extension of linear programming.
- Module 4: LP relaxation. Examples of problems where LP relaxation achieves optimum. Examples where LP/SDP relaxation achieves approximate solution. Integrality gaps.
- Module 5: Rounding, probabilistic roundings, iterative rounding, primal dual methods.
- Module 6 (Optional): Gale-Shapley algorithm, Connection of LP to Cooperative Game Theory core, nucleolus, combinatorial optimization games.
Reference Books
- A. Schrijver, ``Theory of Linear and Integer Programming'', Wiley.
- A. Schrijver, ``Combinatorial Algorithm: Polyhedra and Efficiency, Volume A'', Springer.
- V. Vazirani, ``Approximation Algorithm'', Springer.
- S. Chakraborty, M. Mitra, P. Sarkar, ``A Course on Cooperative Game Theory'', Cambridge University Press.
Course No
CS455
Prerequisites
CS202, CS301
Credit
4
Classes per week
3 Lectures + 1 Tutorial
Syllabus
- Module 1: Foundations of distributed network algorithms - Broadcast, converge-cast, maximal independent set, coloring, leader election, spanning tree algorithms, shortest paths, and routing.
- Module 2: Fundamental concepts in distributed algorithms - Symmetry breaking, locality, synchronizers
- Module 3: Basics of distributed network systems - Communication, synchronization, fault-tolerance, and resource allocation
- Module 4: Applications to real-world networks - Internet, peer-to-peer networks, wireless networks, sensor networks and dynamic networks
- Module 5: Lower bounds using communication complexity, distributed computation of large-scale data, dynamic network algorithms.
Reference Books
- D. Peleg, ``Distributed Computing: A Locality-Sensitive Approach'', SIAM 2000.
- G. Pandurangan, ``Distributed Network Algorithms, a monograph'', Department of CS, University of Houston.
- H. Attiya, J. Welch, ``Distributed Computing: Fundamentals", Simulations and Advanced Topics, McGraw-Hill Publishing, 1998.
- N. Lynch, ``Distributed Algorithms'', Morgan Kaufmann 1996.
- G. Tel, Introduction to Distributed Algorithms, Cambridge University Press 2000.
Corporate Site - This is a contributing Drupal Theme
Design by WeebPal.
Design by WeebPal.