Lianna Hambardzumyan

Hi there! I'm a postdoc at HUJI hosted by Alex Samorodnitsky and Guy Kindler.

I received my PhD in Computer Science from McGill University where I was lucky to be advised by Hamed Hatami, and co-advised by Prakash Panangaden for the first two years.

Prior to that, I received both my bachelor's and masters degrees from Yerevan State University in Informatics and Applied Mathematics.

My current research interests include:

Complexity theory, particularly Communication complexity
Combinatorics
Analysis of Boolean functions

[CV]

Email: lianna.hambardzumyan@mail.huji.ac.il

Office: Rothberg A402

Publications

No Complete Problem for Constant-Cost Randomized Communication

with Yuting Fang, Nathan Harms, and Pooya Hatami
- to appear in 56th Annual ACM Symposium on Theory of Computing (STOC), 2024
An improved protocol for ExactlyN with more than 3 players

with Toniann Pitassi, Suhail Sherif, Morgan Shirley, and Adi Shraibman [ECCC]
- 15th Innovations in Theoretical Computer Science (ITCS), 2024
On depth-3 circuits and covering number: an explicit counter-example

with Hamed Hatami, Ndiamé Ndiaye, [arxiv], 2022
A counter-example to the probabilistic universal graph conjecture via randomized communication complexity
with Hamed Hatami, Pooya Hatami, [arxiv], [doi]
- Discrete Applied Mathematics, Volume 322, 2022, Pages 117-122
Dimension-free Bounds and Structural Results in Communication Complexity
with Hamed Hatami, Pooya Hatami, [ECCC], [doi]
- Israel Journal of Mathematics, 2022
Biasing Boolean Functions and Collective Coin-Flipping Protocols over Arbitrary Product Distributions

with Yuval Filmus, Hamed Hatami, Pooya Hatami, David Zuckerman, [ECCC], [DROPS]
- The 46th International Colloquium on Automata, Languages and Programming (ICALP), 2019
Chang's lemma via Pinsker's inequality

with Yaqiao Li, [arxiv], [doi]
- Discrete Mathematics, Volume 343, Issue 1, 2020
- Canadian Discrete and Algorithmic Mathematics (CanaDAM), 2019
Lower bounds for graph bootstrap percolation via properties of polynomials

with Hamed Hatami, Yingjie Qian, [arxiv], [doi]
- Journal of Combinatorial Theory, Series A, Volume 174, 2020
Graphs, Disjoint Matchings and Some Inequalities

with Vahan Mkrtchyan, [arxiv]

Teaching

McGill University, Winter 2022: COMP 202 - Foundations of Programming
McGill University, Fall 2021: COMP 360 - Algorithm Design

Thesis

Dimension-free Bounds and Structural Results in Communication Complexity

Lianna Hambardzumyan

PhD thesis

Fun stuff

My photography portfolio
My goodreads page