Sitemap

A list of all the posts and pages found on the site. For you robots out there is an XML version available for digesting as well.

Pages

Posts

First Post

less than 1 minute read

Published:

This is a test blog post. I decided to switch my academic page template to academicpages.github.io, and this is the first test post to make sure the blog system works as intended.

portfolio

publications

Neuberg Locus and its Properties

Published in Journal of Classical Geometry, 2013

Neuberg Locus and its properties.

Recommended citation: Banerjee, Debdyuti and Mukherjee, Sayan. "Neuberg Locus And Its Properties." Journal of Classical Geometry, Volume 2 (26) (2013).

Triangles in graphs without bipartite suspensions

Published in Discrete Mathematics (conditionally accepted), 2020

Counting number of triangles in graphs forbidding suspensions of bipartite graphs.

Recommended citation: Mubayi, Dhruv, and Mukherjee, Sayan. "Triangles in graphs without bipartite suspensions." arXiv preprint arXiv:2004.11930 (2020).

Maximum H-free subgraphs

Published in Journal of Combinatorics, 2021

Maximum subgraphs without hypergraph families.

Recommended citation: Mubayi, Dhruv and Mukherjee, Sayan. "Maximum H-free subgraphs." Journal of Combinatorics Volume 12 (2) Pages 185-214 (2021).

Extremal Problems for Graphs and Hypergraphs

Published in University of Illinois at Chicago, 2021

Ph.D. Thesis for Ph.D. in Mathematics defended at University of Illinois at Chicago.

Recommended citation: Mukherjee, Sayan. "Extremal Problems for Graphs and Hypergraphs." Thesis,Department of Mathematics, Statistics and Computer Science, University of Illinois at Chicago (2021).

Neural Sequence Transformation

Published in Computer Graphics Forum; Pacific Graphics Conference 2021, 2021

Using neural networks to perform sequence transformation.

Recommended citation: Mukherjee, Sabyasachi; Mukherjee, Sayan; Hua, Binh-Son; Umetani, Nobuyuki and Meister, Daniel. "Neural Sequence Transformation." Computer Graphics Forum (Wiley), Volume 40, Issue 7, Pages 131-140 (2021).

A Grover search-based algorithm for the list coloring problem

Published in IEEE Transactions on Quantum Engineering, 2022

We analyze the list coloring problem and demonstrate a fast quantum algorithm for it.

Recommended citation: Mukherjee, Sayan. "A Grover search-based algorithm for the list coloring problem." IEEE Transactions on Quantum Engineering Volume 3 (2022).

Tight query complexity bounds for learning graph partitions

Published in Conference on Learning Theory 2022, 2022

Tight query complexity bounds for learning graph partitions.

Recommended citation: Liu, Xizhi and Mukherjee, Sayan. "Tight query complexity bounds for learning graph partitions." arXiv preprint arXiv:2112.07897 (2021).

Stability theorems for some Kruskal-Katona type results

Published in European Journal of Combinatorics (accepted), 2022

Stability theorems for some Kruskal-Katona type results.

Recommended citation: Liu, Xizhi and Mukherjee, Sayan. "Stability theorems for some Kruskal-Katona type results." arXiv preprint arXiv:2006.04848 (2020).

talks

Tight Query Complexity Bounds for Learning Graph Partitions

Published:

Given a partition of a graph into connected components, the membership oracle asserts whether any two vertices of the graph lie in the same component or not. We prove that for $n\ge k\ge 2$, learning the components of an $n$-vertex hidden graph with $k$ components requires at least $(k-1)n-\binom k2$ membership queries. Our result improves on the best known information-theoretic bound of $\Omega(n\log k)$ queries, and exactly matches the query complexity of the algorithm introduced by Reyzin and Srivastava, 2007 for this problem. Additionally, we introduce an oracle that can learn the number of components of $G$ in asymptotically fewer queries than learning the full partition, thus answering another question posed by the same authors. Lastly, we introduce a more applicable version of this oracle, and prove asymptotically tight bounds of $\widetilde\Theta(m)$ queries for both learning and verifying an $m$-edge hidden graph $G$ using it.

teaching

Teaching Assistant

Undergraduate course, University of Illinois at Chicago, Department of Mathematics, Statistics and Computer Science, 2016

Below are the different courses I have taught for at UIC during my Ph.D. from Fall 2016 to Spring 2021. You can find materials relevant to / used during these courses in their respective webpages below. Note that all courses do not have webpages with supplemental material.