Bangalore Theory Seminar Series
144 videos • 1,409 views • by CSAChannel IISc
1
A 2+epsilon approximation algorithm for pre-emptive weighted flow time on a single machine
CSAChannel IISc
Download
2
A 3-Approximation Algorithm for Maximum Independent Set of Rectangles by Arindam Khan
CSAChannel IISc
Download
3
Recent Progress in Online Matching (Part 2): Open Problems in Online Advertising by Zhiyi Huang
CSAChannel IISc
Download
4
Recent progress in online matching (Part -1): Open problems in online advertising by Dr. Zhiyi Huang
CSAChannel IISc
Download
5
Superpolynomial lower bounds against low-depth algebraic circuits - Nutan Limaye
CSAChannel IISc
Download
6
Average Sensitivity of Graph Algorithms by Yuichi Yoshida
CSAChannel IISc
Download
7
Spectral Clustering Oracles in Sublinear Time
CSAChannel IISc
Download
8
Better-Than-2 Approximations for Weighted Tree Augmentation - Vera Traub
CSAChannel IISc
Download
9
Efficient Intervention Design for Learning Causal DAGs, by Karthikeyan Shanmugam
CSAChannel IISc
Download
10
Monotone Arithmetic Lower Bounds Via Communication Complexity - Arkadev Chattopadhyay
CSAChannel IISc
Download
11
Improved (exponential time) algorithms: A case study for Subset Sum and Bin Packing- Jesper Nederlof
CSAChannel IISc
Download
12
Algorithmic advances on metric and graph clustering (Part 1) Vincent Cohen-Addad (Google, Zurich)
CSAChannel IISc
Download
13
Recent developments on ∃R-completeness of packing and other problems by Mikkel Abrahamsen
CSAChannel IISc
Download
14
Algorithmic advances on metric and graph clustering (Part 2) Vincent Cohen-Addad
CSAChannel IISc
Download
15
Min Sum Set Cover and Tail Bounds for Sums of Bernoullis by Jatin Batra
CSAChannel IISc
Download
16
Some Recent Advances in Dynamic Algorithms for Maximum Matching and Minimum Set Cover (Part 2)
CSAChannel IISc
Download
17
Some Recent Advances in Dynamic Algorithms for Maximum Matching and Minimum Set Cover (Part 1)
CSAChannel IISc
Download
18
Playing Unique Games on Certifiable Small-set Expanders by Mitali Bafna (Harvard University)
CSAChannel IISc
Download
19
Matrix Discrepancy from Quantum Communication by Abhishek Shetty (UC Berkeley)
CSAChannel IISc
Download
20
Planar Partition Oracles and When they strike gold by Akash Kumar EPFL Switzerland
CSAChannel IISc
Download
21
Cascaded Norms in Clustering by Eden Chlamtac (Ben Gurion University)
CSAChannel IISc
Download
22
Parameterized Approaches to Kemeny Rank Aggregation by Neeldhara Misra (IIT Gandhinagar)
CSAChannel IISc
Download
23
Online Learning with Hints by Aditya Bhaskara (University of Utah)
CSAChannel IISc
Download
24
Electrical Flows over Spanning Trees by Swati Gupta (Georgia Institute of Technology)
CSAChannel IISc
Download
25
Partitioning over Submodular Structures – Part I by Karthekeyan Chandrasekaran
CSAChannel IISc
Download
26
Partitioning over Submodular Structures – Part II by Karthekeyan Chandrasekaran
CSAChannel IISc
Download
27
Alice in the PA-Land by Maciej Obremski (National University of Singapore)
CSAChannel IISc
Download
28
Near Optimal Split-state Non-malleable Codes by Sai Lakshmi Bhavana (Microsoft Research, India)
CSAChannel IISc
Download
29
New techniques and results for Support Recovery in Mixture Models by Soumyabrata Pal
CSAChannel IISc
Download
30
Finding Adversarially Robust Representations by Aravindan Vijayaraghavan (Northwestern University)
CSAChannel IISc
Download
31
Interventional Complexity of Learning Causal Graphs by Vibhor Porwal (Adobe Research)
CSAChannel IISc
Download
32
Perfect matchings and Quantum Physics by Rishikesh Gajjala
CSAChannel IISc
Download
33
Determinant Maximization : Approximation and Estimation Algorithms by Mohit Singh
CSAChannel IISc
Download
34
Hypergraph expansion, CSPs, and algorithmic decoding of epsilon-balanced codes by Madhur Tulsiani
CSAChannel IISc
Download
35
Online Algorithm for the Minimum Metric Bipartite Matching Problem by Sharath Raghvendra
CSAChannel IISc
Download
36
Scheduling to minimize the Age of Information by Rahul Vaze (TIFR)
CSAChannel IISc
Download
37
Algorithms for learning and testing high-dimensional statistical and causal relations
CSAChannel IISc
Download
38
Public Randomness Extraction with Ephemeral Roles and Worst-Case Corruptions by João Ribeiro (CMU)
CSAChannel IISc
Download
39
Decentralized Bandits in Matching Markets by Karthik Abinav (Facebook)
CSAChannel IISc
Download
40
Local Codes for Insertion and Deletion Errors by Elena Grigorescu (Purdue)
CSAChannel IISc
Download
41
Robust Secretary Algorithms for Packing Integer Programs by Sahil Singla (Georgia Tech)
CSAChannel IISc
Download
42
Correlated Rounding for Correlation Clustering by Alantha Newman
CSAChannel IISc
Download
43
On High Dimensional Expanders and Hardness of Approximation by Max Hopkins
CSAChannel IISc
Download
44
Some NP-hardness Results and An Approximation Algorithm by Mrinalkanti Ghosh
CSAChannel IISc
Download
45
Negative-Weight Single-Source Shortest Paths in Near-linear TimeDanupon Nanongkai
CSAChannel IISc
Download
46
Improved sublinear algorithms for testing permutation freeness by Nithin Varma
CSAChannel IISc
Download
47
Determinant Maximization via Matroid Intersection Algorithms by Aditi Laddha
CSAChannel IISc
Download
48
Spectral sparsification of directed hypergraphs by spanner’s counterpart by Kazusato Oko
CSAChannel IISc
Download
49
Set membership with two classical and quantum probes by Jaikumar Radhakrishnan
CSAChannel IISc
Download
50
The number of leaves in a Boolean decision tree by Jaikumar Radhakrishnan
CSAChannel IISc
Download
51
Approximate Representation of Symmetric Submodular Functions via Hypergraph Cut Functions
CSAChannel IISc
Download
52
Robustly Learning Mixtures of Arbitrary Gaussians in Polynomial Time by Santosh Vempala
CSAChannel IISc
Download
53
Exploring the Gap between Tolerant and Non-tolerant Distribution Testing by Sayantan Sen
CSAChannel IISc
Download
54
Lifelong Learning of Representations with Provable Guarantees by Santosh Vempala (Georgia Tech)
CSAChannel IISc
Download
55
All-Pairs Minimum Cuts in Nearly Quadratic Time Debmalya Panigrahy (Duke)
CSAChannel IISc
Download
56
Survey talk by Amir Abboud on fine-grained complexity by Amir Abboud (Weizmann Institute of Science)
CSAChannel IISc
Download
57
Existence and Computation of Epistemic EFX Allocations by Eklavya Sharma (UIUC)
CSAChannel IISc
Download
58
Model Counting meets F0 Estimation by Arnab Bhattacharyya (NUS, Singapore)
CSAChannel IISc
Download
59
Matroid-convex functions and approximative closure of some polynomial classes by Rohit Gurjar
CSAChannel IISc
Download
60
Quantum Worst-case to Average-case reductions for all linear problems by Sathyawageeswar Subramanian
CSAChannel IISc
Download
61
Probabilistic Hash Functions and Hash Tables by Anshumali Shrivastava
CSAChannel IISc
Download
62
Smoothed Analysis of Online Decision Making by Abhishek Shetty (UC Berkeley)
CSAChannel IISc
Download
63
Low Degree Testing over the Reals by Vipul Arora
CSAChannel IISc
Download
64
Hardness of Approximating Discrete Steiner Tree in L_p metrics by Karthik C. S. (Rutgers University)
CSAChannel IISc
Download
65
Equivalence Test for Read-Once Arithmetic Formulas by Bhargav Thankey
CSAChannel IISc
Download
66
Machine Learning and Logic: Fast and Slow Thinking by Moshe Y. Vardi (Rice University)
CSAChannel IISc
Download
67
Utilizing the CLT Structure in Stochastic Approximations of Sampling Algorithms by Dheeraj Nagaraj
CSAChannel IISc
Download
68
2D expansion in random geometric graphs by Sidhanth Mohanty (UC Berkeley)
CSAChannel IISc
Download
69
Causal Fairness Analysis by Drago Plecko (ETH Zurich)
CSAChannel IISc
Download
70
Title: Private Convex Optimization via Exponential Mechanism by Sivakanth Gopi (MSR, Redmond)
CSAChannel IISc
Download
71
Criticality of AC0-formulae by Prahladh Harsha (TIFR, Mumbai)
CSAChannel IISc
Download
72
Sequential learning in a stochastic multi armed bandit framework by Sandeep Juneja (TIFR, Mumbai)-2
CSAChannel IISc
Download
73
Sequential learning in a stochastic multi armed bandit framework by Sandeep Juneja (TIFR, Mumbai)-1
CSAChannel IISc
Download
74
Hop-Constrained Expander Decompositions, Oblivious Routing, and Distributed Universal Optimality
CSAChannel IISc
Download
75
Online and Bandit Algorithms Beyond ℓ_p Norms by Thomas Kesselheim (University of Bonn)
CSAChannel IISc
Download
76
A PTAS for Unsplittable Flow on a Path by Tobias Mömke (University of Augsburg)
CSAChannel IISc
Download
77
Instance-dependent Sample Complexity Bounds for Zero-sum Matrix Games by Arnab Maiti
CSAChannel IISc
Download
78
Algorithms Approaching the Threshold for Semi-random Planted Clique by Rares-Darius Buhai
CSAChannel IISc
Download
79
Multi-robot planning strategies for spatio-temporal sampling, Sandeep Manjanna (Plaksha University)
CSAChannel IISc
Download
80
The Subspace Flatness Conjecture and Faster Integer Programming by Victor Reis
CSAChannel IISc
Download
81
Learning linear thresholds from label proportions by Rishi Saket (Google Research, India)
CSAChannel IISc
Download
82
Data-driven Social Informatics by Gita Sukthankar (University of Central Florida)
CSAChannel IISc
Download
83
Round-or-Cut Technique for designing Approximation Algorithms for Clustering Problems by Deeparnab C
CSAChannel IISc
Download
84
Integrality Gaps for Random Integer Programs via Discrepancy by Daniel Dadush (CWI, Netherlands)
CSAChannel IISc
Download
85
Moments, Random Walks, and Limits for Spectrum Approximation by Apoorv Vikram Singh (NYU, Tandom)
CSAChannel IISc
Download
86
Tackling Label Corruptions: Univariate Polynomial Regression and Generalized Linear Models
CSAChannel IISc
Download
87
The Price of Equity with Binary Valuations and Few Agent Types by Aditi Sethia (IIT Gandhinagar)
CSAChannel IISc
Download
88
Differential Privacy in Multi-armed Bandits by Sayak Ray Chowdhury (Microsoft Research, Bangalore)
CSAChannel IISc
Download
89
Title: Causal Inference and Large Language Models: A New Frontier by Amit Sharma Part 1
CSAChannel IISc
Download
90
Title: Causal Inference and Large Language Models: A New Frontier by Amit Sharma Part 2
CSAChannel IISc
Download
91
First Part of Lecture Series on Causality by Dr. Karthikeyan Shanmugam
CSAChannel IISc
Download
92
Second Part of Lecture Series on Causality by Dr. Karthikeyan Shanmugam
CSAChannel IISc
Download
93
Third Part of Lecture Series on Causality by Dr. Karthikeyan Shanmugam
CSAChannel IISc
Download
94
Learning to make customized user predictions through preference elicitation by Aadirupa Saha
CSAChannel IISc
Download
95
Robustly Learning Affine Transformations with Asymptotically Optimal Error by He Jia (Georgia Tech)
CSAChannel IISc
Download
96
Random Separating Hyperplane theorem with applications to Topic Modelling by Chiranjib Bhattacharyya
CSAChannel IISc
Download
97
Fourth Part of Lecture Series on Causality by Dr. Karthikeyan Shanmugam
CSAChannel IISc
Download
98
Fifth Part of Lecture Series on Causality by Dr. Karthikeyan Shanmugam
CSAChannel IISc
Download
99
Sixth Part of Lecture Series on Causality by Dr. Karthikeyan Shanmugam
CSAChannel IISc
Download
100
Approximation Algorithms for Network Design in Non-Uniform Fault Models by Prof. Chandra Chekuri
CSAChannel IISc
Download
101
Sample Complexity of Distinguishing Cause from Effect by Saravanan Kandasamy (Cornell University)
CSAChannel IISc
Download
102
Seventh Part of Lecture Series on Causality by Dr. Karthikeyan Shanmugam
CSAChannel IISc
Download
103
Eighth Part of Lecture Series on Causality by Dr. Karthikeyan Shanmugam
CSAChannel IISc
Download
104
Hardness of Approximation of Diameter Clustering by Karthik C. S. (Rutgers University)
CSAChannel IISc
Download
105
Detecting Hidden Communities by Power Iterations with Connections to Vanilla Spectral Algorithms
CSAChannel IISc
Download
106
Ninth Part of Lecture Series on Causality by Dr. Karthikeyan Shanmugam
CSAChannel IISc
Download
107
The Sampling Problem Through The Lens of Optimization : Recent Advances and Insights by Aniket Das
CSAChannel IISc
Download
108
Tenth Part of Lecture Series on Causality by Dr. Karthikeyan Shanmugam
CSAChannel IISc
Download
109
Best of Both Worlds in Fair Division by Rohit Vaish (IIT Delhi)
CSAChannel IISc
Download
110
Provably Learning a Multi-head Attention Layer by Sitan Chen (Harvard)
CSAChannel IISc
Download
111
Query-Efficient Algorithms to Find the Unique Nash Equilibrium in a Two-Player Zero-Sum Matrix Game
CSAChannel IISc
Download
112
Optimized Distribution of Quantum Circuits by Ranjani Sundaram (Stony Brook University)
CSAChannel IISc
Download
113
Title: Robust Reinforcement Learning using Offline Data by Kishan Panaganti (Caltech)
CSAChannel IISc
Download
114
Offline Data Enhanced On-Policy Policy Gradient by Ayush Sekhari (MIT, Boston)
CSAChannel IISc
Download
115
Optimized Distribution of Quantum Circuits by Ranjani Sundaram (Stony Brook University)
CSAChannel IISc
Download
116
PAC Bounds and Intractability for Learning from Label Proportions, by Rishi Saket
CSAChannel IISc
Download
117
On MAP Inference of Ferromagnetic Potts models and Nonsymmetric Determinantal Point Processes
CSAChannel IISc
Download
118
Locally Stationary Distributions: A Framework for Analyzing Slow-Mixing Markov Chains
CSAChannel IISc
Download
119
List decoding and Higher Order MDS codes, by Manik Dhar
CSAChannel IISc
Download
120
The Rate of Interactive Codes Is Bounded Away from 1, by Raghuvansh Saxena
CSAChannel IISc
Download
121
Fourier Growth for Communication Protocols for XOR functions, by Uma Girish
CSAChannel IISc
Download
122
Optimal PAC Bounds without Uniform Convergence, by Abhishek Shetty
CSAChannel IISc
Download
123
Distinct Elements in Streams and the Klee's Measure Problem by Sourav Chakraborty (ISI Kolkata)
CSAChannel IISc
Download
124
Ticketed Learning-Unlearning Schemes by Ayush Sekhari (MIT, Boston)
CSAChannel IISc
Download
125
Interplay of submodularity and randomness, by Arjun Ramachandra
CSAChannel IISc
Download
126
Leveraging Large Language Models for Causal Inference, by Rohit Bhattacharya
CSAChannel IISc
Download
127
Scheduling with cardinality dependent unavailability periods, by G Jaykrishnan
CSAChannel IISc
Download
128
Controlling Distributed Optimization from a Stochastic Oracle, by Adit Jain
CSAChannel IISc
Download
129
Fast Algorithms and Data Structures for Regression, by Deeksha Adil
CSAChannel IISc
Download
130
Linear Time Streaming Algorithms for Heavy Tailed Statistics by Aniket Das
CSAChannel IISc
Download
131
Covering a graph with dense subgraphs: theory and some practice, by Sabyasachi Basu
CSAChannel IISc
Download
132
Constant-Factor Approximation Algorithms for Convex Cover and Hidden Set in a Simple Polygon
CSAChannel IISc
Download
133
Advances and Challenges in Fair Division: Quantiles, Subsidies, and Randomization, by Vishnu Narayan
CSAChannel IISc
Download
134
Efficient Statistics with Unknown Truncation, Polynomial Time Algorithms, Beyond Gaussians
CSAChannel IISc
Download
135
Hardness of Packing Simple Polygons with Unit Squares, by Jack Tor Stade
CSAChannel IISc
Download
136
Piercing axis-parallel boxes with axis-parallel k-flats by Soumi Nandi
CSAChannel IISc
Download
137
Outlier Robust Multivariate Polynomial Regression by Vipul Arora
CSAChannel IISc
Download
138
Making Quantum Query Algorithms Robust to a Faulty Oracle, by Manaaswi Parashar
CSAChannel IISc
Download
139
Inapproximability of Sparsest Vector in a Real Subspace, by Vijay Bhattiprolu
CSAChannel IISc
Download
140
Uncertainty Quantification for Large Language Models, by Shubhendu Trivedi
CSAChannel IISc
Download
141
Studies in Decision-Making, by Kavya Ravichandran
CSAChannel IISc
Download
142
A Primer on Distributed Computing, by Sagnik Mukhopadhyay Part 1
CSAChannel IISc
Download
143
A Primer on Distributed Computing, by Sagnik Mukhopadhyay Part 2
CSAChannel IISc
Download
144
Characterizations of threshold classifiers, by Mohit Sharma
CSAChannel IISc
Download