Instructor: Prof. Amit Kumar
COL866 will focus on online algorithms and online learning. Online algorithms are useful when the entire input is not given in advance, but arrives over time. Online learning problems refer to settings where one needs to learn the best solution for a problem by observing inputs which arrive over time. The first part of the course will focus on online algorithms, and the second part will focus on online learning and connections between the two streams. Week wise tentative schedule is given below. In terms of background, familiarity with algorithms and basic calculus/linear algebra would suffice. There is no textbook for this course, but reading material will be given.
Week 1: Introduction to online algorithms, competitive analysis. SRPT, Ski rental and randomized online algorithms. Unweighted Paging: LRU and randomized marking algorithm.
Week 2: Online network design: online Steiner tree, online Steiner forest. Online routing and call admission.
Week 3: Online Load Balancing: parallel and restricted parallel machines. Introduction to linear programming, duality theory.
Week 4: Rounding of linear programs. Randomized rounding and Chernoff Bounds. Applications
Week 5: Online weighted set cover and primal-dual interpretation Online weighted paging, maintaining convex combination of integral solutions online
Week 6: Online Scheduling: flow-time minimization on identical machines. Online scheduling: flow-time minimization on unrelated machines and dual fitting.
Week 7: K-server problem: Double cover algorithm, work function algorithm
Week 8: Online bipartite matching, adwords problem. Online fractional matching.
Week 9: Learning with experts, multiplicative experts and regret minimization. Application: solving linear programs.
Week 10: Application of multiplicative update: fast algorithms for max-flow. Online convex Optimization: follow the leader, follow the regularized leader
Week 11: Online gradient descent, Applications. Bregman Divergence, Fenchel duality
Week 12: Mirror Descent. Use of mirror descent based ideas for design of online algorithms.
Week 13: Beyond worst case analysis: Stochastic arrival models. Secretary problems, online facility location.
Week 14: Beyond worst case: Online algorithms with recourse. Steiner tree, load balancing
Instructor: Prof. Srikanta Bedathur
I am offering COL865: Special Topics in Computer Applications with focus on the use of machine learning and deep learning techniques for understanding of tabular and multi-modal data.
The course will mostly consist of reading, presenting and critically examining important research publications in these areas, and one course project.
It is necessary to have formal background (in terms of coursework) in machine learning and deep learning; preferable to have some knowledge of one or more of: relational databases, computer vision and NLP; and finally, some familiarity with data cleaning techniques would be helpful though not necessary.
Contact me for more details, and the course webpage will be available by the end of June.
Instructor: Prof. Rohit Vaish
This course is situated at the intersection of theoretical computer science, artificial intelligence, and economics. We will explore the mathematical and algorithmic foundations of problems that involve making a collective decision from individual preferences. The lectures will cover classical topics in this area such as voting and fair division as well as modern paradigms including participatory budgeting, fair representation, and organ exchanges. Further details can be found on the course website:
https://rohitvaish.in/Teaching/2022-Fall/
Feel free to reach out if you have any questions.
Instructor: Prof. Maya Ramanath
Pre-requisite: You should have completed COL362/632.
Summary: In this course, we will study different approaches of enriching SQL query results with explanations that provide insight into why an answer becomes part of an answer set, or how it is generated, or, more interestingly, why not an entity is part of an answer set. We will mainly focus on prior work that employ provenance models for providing such explanations from different perspectives. For a high level overview (which we will also cover in the first couple of meetings), go through this survey: Provenance in Databases: Why, How, and Where (survey) https://homepages.inf.ed.ac.uk/jcheney/publications/provdbsurvey.pdf
How the course will be run: This is a seminar course where students will be expected to do lots of paper reading and present detailed descriptions and critiques of the papers they read. We plan to meet in a fairly long 2-3 hour slot, once a week – enough to cover 1-2 papers. There will be a short project and/or survey writing assignment (based on the number of participants) as part of the evaluation.
Instructor: Prof. Anurag Mittal
The course will be on Deep Learning with a special focus on Computer Vision applications. The following topics will be covered:
Overview of Computer Vision and other AI applications, Image Classification, Neural Networks, Multi-layer Perceptrons, Activation Functions, Convolutional Neural Networks, Feature visualization and inversion.
Training Neural Networks - Loss Functions, Optimization, stochastic gradient descent, Backpropagation, initialization, dropout, batch normalization, Update rules, ensembles, data augmentation, transfer learning. Advanced CNN Architectures, RNNs, LSTM, GRU.
Application of Deep Learning to: Image Classification, Object Detection, Segmentation, Semantic segmentation, Instance segmentation, style transfer, Human Pose Estimation, Video classification, Language modeling, Image and Video captioning, visual question answering,
Attention. Generative Methods: Variational Auto-Encoders and Generative Adversarial Networks, pixelRNN. Contrastive Learning. Unsupervised, semi-supervised and self-supervised learning approaches. Zero-shot and low-shot learning. Other latest ideas and topics as time permits.
Instructor: Prof. Ashok K. Bhateja
Course Contents:
Secret Sharing, Secure Multi-Party Computation (SMPC)
Lattice Based Cryptology: Introduction to Lattices, NTRU Cryptosystem, Lattice Signature Scheme, Cryptanalysis of lattice-based cryptosystems.
Elliptic curves
Pairing-Based Cryptography, Weil Pairing, Tate Pairing, key exchange using elliptic curves, Identity-Based Encryption, Attribute-Based Encryption, Functional Encryption
Homomorphic Encryption: Goldwasser-Mical and Paillier cryptosystems, Homomorphic secret sharing, Homomorphic signatures, somewhat and fully homomorphic encryption.
This is an advanced course on Cryptography and Cryptanalysis. The course will consist of reading, presenting and critically examining important research publications in these areas.
Pre-requisite: COL759 (Cryptography & Computer Security) or MTL730 or equivalent
Evaluation: Assignments and Exams.
Contact me for more details, if required.
Instructor: Prof. Tanu Malik, DePaul University
Overview: This course will provide an introduction to Linux containers, which virtualize different system resources. It will provide a hands-on experience with the Linux infrastructure used for creating containers, provision containers with different resource requirements, and operate them in privileged and non-privileged settings. The overall goal is to develop a deeper knowledge of Linux system calls and appreciation of systems concepts of isolation and file layering. We will also examine alternative isolation and file layering approaches (e.g., chroot, seccomp, ebpf)
Course webpage: https://dice.cs.depaul.edu/courses/882/index.html
Instructor: Prof. Subodh Sharma
Blockchain is an emerging technology platform for developing decentralised applications with claims to offer strong cryptographic guarantees of tamper resistance, immutability and verifiability. While the claim to fame for Blockchain is cryptocurrencies such as Bitcoin, its role as a technology solution extends beyond them. In this course, we will learn the main technological underpinnings (both theoretical and practical) behind Blockchain and discuss its (possible) role in shaping business processes. We will also briefly discuss the politics and regulations surrounding this technology. The course does not have any prerequisites except eagerness to learn and program.
The plan is cover a reasonable subset of the following topics:
The course will require active participation from the participants and will involve no more than two assignments. For any further queries, feel free to write an email to me.
Instructor: Prof. Aaditeshwar Seth
The course will introduce common fault-lines where ethical issues arise in the use of web-based computing technologies, build skills through which systems can be analyzed to uncover these issues, apply different methods to address these issues, and show that ensuring that responsible outcomes arise from technologies goes beyond just building the technologies.
Course contents will include the application of ethical theories – consequentialism, deontological, virtue ethics; concerns that arise at different layers in an information system – user interface design, data and privacy, algorithms and artificial intelligence, multi-stakeholder system design, and management policies; methods to address these concerns, such as algorithmic auditing, fairness in classification systems, fairness policies coded into the system, differential privacy, private communication, and ongoing management of systems; design methods such as participatory design and action research; the political economy of web technologies; theories of technology determinism and social control of technology
The teaching methodology will be a mix of lectures and paper readings. Evaluation will be based on exams and a term project. Readings from previous offerings of the course can be found here: http://act4d.iitd.ernet.in/act4d/index.php?option=com_content&view=article&id=37&Itemid=45