Resource Allocation Problems in Large-Scale Networks

STCS Seminar

Speaker:

Abhishek Sinha

Organisers:

Time:

Tuesday, 21 September 2021, 16:00 to 17:15

Optimal resource allocation in networks gives rise to some of the most fundamental problems at the intersection of algorithms, stochastic processes, and learning.

Commuting Matrices and Multivariate Multiplicity

STCS Student Seminar

Speaker:

Anamay Tengse, TIFR

Organisers:

Eeshan Modak

Time:

Friday, 17 September 2021, 17:15 to 18:15

We know that for matrices A and B, AB is not the same as BA in general. But suppose B is a polynomial in A, like B = A^2 - 3A + I (note I = A^0). Then AB is indeed the same as BA.

Quasi-transitive tilings of the plane

STCS Seminar

Speaker:

Arun Maiti

Organisers:

Hariharan Narayanan

Time:

Tuesday, 7 September 2021, 16:00 to 17:00

Tiling of a surface is acted upon by its automorphism group. The tilings with single vertex orbit, the transitive tilings, are well studied since antiquity.

Linear Matroid Intersection is in Pseudo-deterministic NC

STCS Student Seminar

Speaker:

Sumanta Ghosh

Organisers:

Prerona Chatterjee

Time:

Friday, 3 September 2021, 17:15 to 18:15

A pseudo-deterministic NC algorithm for a search problem is an RNC algorithm that, for a given input, outputs a fixed solution with high probability.

The complexity of approximating Satisfiable CSPs

STCS Seminar

Speaker:

Amey Bhangale

Organisers:

Prahladh Harsha

Time:

Tuesday, 31 August 2021, 16:00 to 17:00

Webpage:

https://sites.google.com/view/amey-bhangale/home

Raghavendra's famous result from 2008 fully characterizes the inapproximability of every maximum constraint satisfaction problem (Max-CSP). However, the result inherently loses perfect completeness.

Project: An algorithm for the multiplicity Schwartz-Zippel lemma

Project Presentation

Speaker:

Aparna Shankar, TIFR

Organisers:

Prahladh Harsha

Time:

Friday, 27 August 2021, 15:00 to 16:00

The multiplicity Schwartz-Zippel lemma provides a bound on the total multiplicity of zeroes of a low-degree polynomial within a product set.

Paper Presentation

Paper Presentation

Speaker:

Varun Ramanathan, TIFR

Organisers:

Prahladh Harsha

Time:

Friday, 27 August 2021, 14:00 to 15:00

Paper: Michael Saks and Rahul Santhanam, "Circuit Lower Bounds from NP-Hardness of MCSP Under Turing Reductions"
https://drops.dagstuhl.de/opus/volltexte/2020/12578/

Paper Presentation

Paper Presentation

Speaker:

Praveen Sai Chinthaginjala, TIFR

Organisers:

Prahladh Harsha

Time:

Friday, 27 August 2021, 12:00 to 13:00

Paper: Nikhil R. Devanur, Zhiyi Huang. "Primal Dual Gives Almost Optimal Energy-Efficient Online Algorithms"
https://dl.acm.org/doi/abs/10.1145/3155297

Paper Presentation

Paper Presentation

Speaker:

Hari Krishnan P A, TIFR

Organisers:

Prahladh Harsha

Time:

Friday, 27 August 2021, 11:00 to 12:00

"Paper: Yuchen Zhang, John C Duchi, Michael I Jordan, Martin J Wainwright, Information-theoretic lower bounds for distributed statistical estimation with communication constraints"

Paper Presentation

Paper Presentation

Speaker:

Pranshu Gaba, TIFR

Organisers:

Prahladh Harsha

Time:

Friday, 27 August 2021, 10:00 to 11:00

Paper: Nachum Dershowitz and Yuri Gurevich, "A Natural Axiomatization of Computability and Proof of Church's Thesis"
https://doi.org/10.2178/bsl/1231081370

Search form

Speaker:

Organisers:

Time:

Organisers:

Time:

Speaker:

Organisers:

Time:

Speaker:

Organisers:

Time:

Speaker:

Organisers:

Time:

Webpage:

Organisers:

Time:

Organisers:

Time:

Organisers:

Time:

Organisers:

Time:

Organisers:

Time:

Pages