UG Elective Courses

CS451

CS451 : Modern Cryptology

Course No:

CS451

Credit:

4

Classes per week:

3 Lectures + 1 Tutorial

Syllabus:

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.

Reference Books:

J. Katz and Y. Lindell, Introduction to Modern Cryptography. CRC, 2014.

CS452

CS452 : Agorithmic Coding Theory

Course No:

CS452

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.

CS453

CS453 : Complexity Theory

Course No:

CS453

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.

CS454

CS454 : Linear Programming and Combinatorial Optimization

Course No:

CS454

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.

CS455

CS455 : Distributed Network Algorithms

Course No:

CS455

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.

NISER

UG Elective Courses