Search Results

Documents authored by Hosseini, Kaave

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.82
Refuting Approaches to the Log-Rank Conjecture for XOR Functions

Authors: Hamed Hatami, Kaave Hosseini, Shachar Lovett, and Anthony Ostuni

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
The log-rank conjecture, a longstanding problem in communication complexity, has persistently eluded resolution for decades. Consequently, some recent efforts have focused on potential approaches for establishing the conjecture in the special case of XOR functions, where the communication matrix is lifted from a boolean function, and the rank of the matrix equals the Fourier sparsity of the function, which is the number of its nonzero Fourier coefficients. In this note, we refute two conjectures. The first has origins in Montanaro and Osborne (arXiv'09) and is considered in Tsang, Wong, Xie, and Zhang (FOCS'13), and the second is due to Mande and Sanyal (FSTTCS'20). These conjectures were proposed in order to improve the best-known bound of Lovett (STOC'14) regarding the log-rank conjecture in the special case of XOR functions. Both conjectures speculate that the set of nonzero Fourier coefficients of the boolean function has some strong additive structure. We refute these conjectures by constructing two specific boolean functions tailored to each.
Cite as

Hamed Hatami, Kaave Hosseini, Shachar Lovett, and Anthony Ostuni. Refuting Approaches to the Log-Rank Conjecture for XOR Functions. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 82:1-82:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{hatami_et_al:LIPIcs.ICALP.2024.82,
  author =	{Hatami, Hamed and Hosseini, Kaave and Lovett, Shachar and Ostuni, Anthony},
  title =	{{Refuting Approaches to the Log-Rank Conjecture for XOR Functions}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{82:1--82:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.82},
  URN =		{urn:nbn:de:0030-drops-202252},
  doi =		{10.4230/LIPIcs.ICALP.2024.82},
  annote =	{Keywords: Communication complexity, log-rank conjecture, XOR functions, additive structure}
}
Document
DOI: 10.4230/LIPIcs.CCC.2023.1
Separation of the Factorization Norm and Randomized Communication Complexity

Authors: Tsun-Ming Cheung, Hamed Hatami, Kaave Hosseini, and Morgan Shirley

Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)

Abstract
In an influential paper, Linial and Shraibman (STOC '07) introduced the factorization norm as a powerful tool for proving lower bounds against randomized and quantum communication complexities. They showed that the logarithm of the approximate γ₂-factorization norm is a lower bound for these parameters and asked whether a stronger lower bound that replaces approximate γ₂ norm with the γ₂ norm holds. We answer the question of Linial and Shraibman in the negative by exhibiting a 2ⁿ×2ⁿ Boolean matrix with γ₂ norm 2^Ω(n) and randomized communication complexity O(log n). As a corollary, we recover the recent result of Chattopadhyay, Lovett, and Vinyals (CCC '19) that deterministic protocols with access to an Equality oracle are exponentially weaker than (one-sided error) randomized protocols. In fact, as a stronger consequence, our result implies an exponential separation between the power of unambiguous nondeterministic protocols with access to Equality oracle and (one-sided error) randomized protocols, which answers a question of Pitassi, Shirley, and Shraibman (ITSC '23). Our result also implies a conjecture of Sherif (Ph.D. thesis) that the γ₂ norm of the Integer Inner Product function (IIP) in dimension 3 or higher is exponential in its input size.
Cite as

Tsun-Ming Cheung, Hamed Hatami, Kaave Hosseini, and Morgan Shirley. Separation of the Factorization Norm and Randomized Communication Complexity. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 1:1-1:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{cheung_et_al:LIPIcs.CCC.2023.1,
  author =	{Cheung, Tsun-Ming and Hatami, Hamed and Hosseini, Kaave and Shirley, Morgan},
  title =	{{Separation of the Factorization Norm and Randomized Communication Complexity}},
  booktitle =	{38th Computational Complexity Conference (CCC 2023)},
  pages =	{1:1--1:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-282-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{264},
  editor =	{Ta-Shma, Amnon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2023.1},
  URN =		{urn:nbn:de:0030-drops-182714},
  doi =		{10.4230/LIPIcs.CCC.2023.1},
  annote =	{Keywords: Factorization norms, randomized communication complexity}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2023.42
Online Learning and Disambiguations of Partial Concept Classes

Authors: Tsun-Ming Cheung, Hamed Hatami, Pooya Hatami, and Kaave Hosseini

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract
In a recent article, Alon, Hanneke, Holzman, and Moran (FOCS '21) introduced a unifying framework to study the learnability of classes of partial concepts. One of the central questions studied in their work is whether the learnability of a partial concept class is always inherited from the learnability of some "extension" of it to a total concept class. They showed this is not the case for PAC learning but left the problem open for the stronger notion of online learnability. We resolve this problem by constructing a class of partial concepts that is online learnable, but no extension of it to a class of total concepts is online learnable (or even PAC learnable).
Cite as

Tsun-Ming Cheung, Hamed Hatami, Pooya Hatami, and Kaave Hosseini. Online Learning and Disambiguations of Partial Concept Classes. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 42:1-42:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{cheung_et_al:LIPIcs.ICALP.2023.42,
  author =	{Cheung, Tsun-Ming and Hatami, Hamed and Hatami, Pooya and Hosseini, Kaave},
  title =	{{Online Learning and Disambiguations of Partial Concept Classes}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{42:1--42:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.42},
  URN =		{urn:nbn:de:0030-drops-180946},
  doi =		{10.4230/LIPIcs.ICALP.2023.42},
  annote =	{Keywords: Online learning, Littlestone dimension, VC dimension, partial concept class, clique vs independent set, Alon-Saks-Seymour conjecture, Standard Optimal Algorithm, PAC learning}
}
Document
DOI: 10.4230/LIPIcs.CCC.2020.18
Sign Rank vs Discrepancy

Authors: Hamed Hatami, Kaave Hosseini, and Shachar Lovett

Published in: LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020)

Abstract
Sign-rank and discrepancy are two central notions in communication complexity. The seminal work of Babai, Frankl, and Simon from 1986 initiated an active line of research that investigates the gap between these two notions. In this article, we establish the strongest possible separation by constructing a boolean matrix whose sign-rank is only 3, and yet its discrepancy is 2^{-Ω(n)}. We note that every matrix of sign-rank 2 has discrepancy n^{-O(1)}. Our result in particular implies that there are boolean functions with O(1) unbounded error randomized communication complexity while having Ω(n) weakly unbounded error randomized communication complexity.
Cite as

Hamed Hatami, Kaave Hosseini, and Shachar Lovett. Sign Rank vs Discrepancy. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 18:1-18:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{hatami_et_al:LIPIcs.CCC.2020.18,
  author =	{Hatami, Hamed and Hosseini, Kaave and Lovett, Shachar},
  title =	{{Sign Rank vs Discrepancy}},
  booktitle =	{35th Computational Complexity Conference (CCC 2020)},
  pages =	{18:1--18:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-156-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{169},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2020.18},
  URN =		{urn:nbn:de:0030-drops-125700},
  doi =		{10.4230/LIPIcs.CCC.2020.18},
  annote =	{Keywords: Discrepancy, sign rank, Unbounded-error communication complexity, weakly unbounded error communication complexity}
}
Document
DOI: 10.4230/LIPIcs.CCC.2019.13
Optimality of Linear Sketching Under Modular Updates

Authors: Kaave Hosseini, Shachar Lovett, and Grigory Yaroslavtsev

Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)

Abstract
We study the relation between streaming algorithms and linear sketching algorithms, in the context of binary updates. We show that for inputs in n dimensions, the existence of efficient streaming algorithms which can process Omega(n^2) updates implies efficient linear sketching algorithms with comparable cost. This improves upon the previous work of Li, Nguyen and Woodruff [Yi Li et al., 2014] and Ai, Hu, Li and Woodruff [Yuqing Ai et al., 2016] which required a triple-exponential number of updates to achieve a similar result for updates over integers. We extend our results to updates modulo p for integers p >= 2, and to approximation instead of exact computation.
Cite as

Kaave Hosseini, Shachar Lovett, and Grigory Yaroslavtsev. Optimality of Linear Sketching Under Modular Updates. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 13:1-13:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{hosseini_et_al:LIPIcs.CCC.2019.13,
  author =	{Hosseini, Kaave and Lovett, Shachar and Yaroslavtsev, Grigory},
  title =	{{Optimality of Linear Sketching Under Modular Updates}},
  booktitle =	{34th Computational Complexity Conference (CCC 2019)},
  pages =	{13:1--13:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-116-0},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{137},
  editor =	{Shpilka, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2019.13},
  URN =		{urn:nbn:de:0030-drops-108355},
  doi =		{10.4230/LIPIcs.CCC.2019.13},
  annote =	{Keywords: communication complexity, linear sketching, streaming algorithm}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2019.13
Torus Polynomials: An Algebraic Approach to ACC Lower Bounds

Authors: Abhishek Bhrushundi, Kaave Hosseini, Shachar Lovett, and Sankeerth Rao

Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)

Abstract
We propose an algebraic approach to proving circuit lower bounds for ACC^0 by defining and studying the notion of torus polynomials. We show how currently known polynomial-based approximation results for AC^0 and ACC^0 can be reformulated in this framework, implying that ACC^0 can be approximated by low-degree torus polynomials. Furthermore, as a step towards proving ACC^0 lower bounds for the majority function via our approach, we show that MAJORITY cannot be approximated by low-degree symmetric torus polynomials. We also pose several open problems related to our framework.
Cite as

Abhishek Bhrushundi, Kaave Hosseini, Shachar Lovett, and Sankeerth Rao. Torus Polynomials: An Algebraic Approach to ACC Lower Bounds. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 13:1-13:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{bhrushundi_et_al:LIPIcs.ITCS.2019.13,
  author =	{Bhrushundi, Abhishek and Hosseini, Kaave and Lovett, Shachar and Rao, Sankeerth},
  title =	{{Torus Polynomials: An Algebraic Approach to ACC Lower Bounds}},
  booktitle =	{10th Innovations in Theoretical Computer Science Conference (ITCS 2019)},
  pages =	{13:1--13:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-095-8},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{124},
  editor =	{Blum, Avrim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.13},
  URN =		{urn:nbn:de:0030-drops-101066},
  doi =		{10.4230/LIPIcs.ITCS.2019.13},
  annote =	{Keywords: Circuit complexity, ACC, lower bounds, polynomials}
}
Document
DOI: 10.4230/LIPIcs.CCC.2018.1
Pseudorandom Generators from Polarizing Random Walks

Authors: Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, and Shachar Lovett

Published in: LIPIcs, Volume 102, 33rd Computational Complexity Conference (CCC 2018)

Abstract
We propose a new framework for constructing pseudorandom generators for n-variate Boolean functions. It is based on two new notions. First, we introduce fractional pseudorandom generators, which are pseudorandom distributions taking values in [-1,1]^n. Next, we use a fractional pseudorandom generator as steps of a random walk in [-1,1]^n that converges to {-1,1}^n. We prove that this random walk converges fast (in time logarithmic in n) due to polarization. As an application, we construct pseudorandom generators for Boolean functions with bounded Fourier tails. We use this to obtain a pseudorandom generator for functions with sensitivity s, whose seed length is polynomial in s. Other examples include functions computed by branching programs of various sorts or by bounded depth circuits.
Cite as

Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, and Shachar Lovett. Pseudorandom Generators from Polarizing Random Walks. In 33rd Computational Complexity Conference (CCC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 102, pp. 1:1-1:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{chattopadhyay_et_al:LIPIcs.CCC.2018.1,
  author =	{Chattopadhyay, Eshan and Hatami, Pooya and Hosseini, Kaave and Lovett, Shachar},
  title =	{{Pseudorandom Generators from Polarizing Random Walks}},
  booktitle =	{33rd Computational Complexity Conference (CCC 2018)},
  pages =	{1:1--1:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-069-9},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{102},
  editor =	{Servedio, Rocco A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2018.1},
  URN =		{urn:nbn:de:0030-drops-88880},
  doi =		{10.4230/LIPIcs.CCC.2018.1},
  annote =	{Keywords: AC0, branching program, polarization, pseudorandom generators, random walks, Sensitivity}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact