Search Results

Documents authored by Ganor, Anat

Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2018.12
Communication Complexity of Correlated Equilibrium with Small Support

Authors: Anat Ganor and Karthik C. S.

Published in: LIPIcs, Volume 116, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)

Abstract
We define a two-player N x N game called the 2-cycle game, that has a unique pure Nash equilibrium which is also the only correlated equilibrium of the game. In this game, every 1/poly(N)-approximate correlated equilibrium is concentrated on the pure Nash equilibrium. We show that the randomized communication complexity of finding any 1/poly(N)-approximate correlated equilibrium of the game is Omega(N). For small approximation values, our lower bound answers an open question of Babichenko and Rubinstein (STOC 2017).
Cite as

Anat Ganor and Karthik C. S.. Communication Complexity of Correlated Equilibrium with Small Support. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 12:1-12:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{ganor_et_al:LIPIcs.APPROX-RANDOM.2018.12,
  author =	{Ganor, Anat and C. S., Karthik},
  title =	{{Communication Complexity of Correlated Equilibrium with Small Support}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)},
  pages =	{12:1--12:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-085-9},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{116},
  editor =	{Blais, Eric and Jansen, Klaus and D. P. Rolim, Jos\'{e} and Steurer, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2018.12},
  URN =		{urn:nbn:de:0030-drops-94163},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2018.12},
  annote =	{Keywords: Correlated equilibrium, Nash equilibrium, Communication complexity}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2018.11
A Candidate for a Strong Separation of Information and Communication

Authors: Mark Braverman, Anat Ganor, Gillat Kol, and Ran Raz

Published in: LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)

Abstract
The weak interactive compression conjecture asserts that any two-party communication protocol with communication complexity C and information complexity I can be compressed to a protocol with communication complexity poly(I)polylog(C). We describe a communication problem that is a candidate for refuting that conjecture. Specifically, while we show that the problem can be solved by a protocol with communication complexity C and information complexity I=polylog(C), the problem seems to be hard for protocols with communication complexity poly(I)polylog(C)=polylog(C).
Cite as

Mark Braverman, Anat Ganor, Gillat Kol, and Ran Raz. A Candidate for a Strong Separation of Information and Communication. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 11:1-11:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{braverman_et_al:LIPIcs.ITCS.2018.11,
  author =	{Braverman, Mark and Ganor, Anat and Kol, Gillat and Raz, Ran},
  title =	{{A Candidate for a Strong Separation of Information and Communication}},
  booktitle =	{9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
  pages =	{11:1--11:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-060-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{94},
  editor =	{Karlin, Anna R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.11},
  URN =		{urn:nbn:de:0030-drops-83322},
  doi =		{10.4230/LIPIcs.ITCS.2018.11},
  annote =	{Keywords: communication complexity, amortized communication complexity, communication compression, direct sum, information complexity}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2014.618
Two Sides of the Coin Problem

Authors: Gil Cohen, Anat Ganor, and Ran Raz

Published in: LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)

Abstract
In the coin problem, one is given n independent flips of a coin that has bias b > 0 towards either Head or Tail. The goal is to decide which side the coin is biased towards, with high confidence. An optimal strategy for solving the coin problem is to apply the majority function on the n samples. This simple strategy works as long as b > c(1/sqrt n) for some constant c. However, computing majority is an impossible task for several natural computational models, such as bounded width read once branching programs and AC^0 circuits. Brody and Verbin proved that a length n, width w read once branching program cannot solve the coin problem for b < O(1/(log n)^w). This result was tightened by Steinberger to O(1/(log n)^(w-2)). The coin problem in the model of AC^0 circuits was first studied by Shaltiel and Viola, and later by Aaronson who proved that a depth d size s Boolean circuit cannot solve the coin problem for b < O(1/(log s)^(d+2)). This work has two contributions: 1. We strengthen Steinberger's result and show that any Santha-Vazirani source with bias b < O(1/(log n)^(w-2)) fools length n, width w read once branching programs. In other words, the strong independence assumption in the coin problem is completely redundant in the model of read once branching programs, assuming the bias remains small. That is, the exact same result holds for a much more general class of sources. 2. We tighten Aaronson's result and show that a depth d, size s Boolean circuit cannot solve the coin problem for b < O(1/(log s)^(d-1)). Moreover, our proof technique is different and we believe that it is simpler and more natural.
Cite as

Gil Cohen, Anat Ganor, and Ran Raz. Two Sides of the Coin Problem. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 618-629, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{cohen_et_al:LIPIcs.APPROX-RANDOM.2014.618,
  author =	{Cohen, Gil and Ganor, Anat and Raz, Ran},
  title =	{{Two Sides of the Coin Problem}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  pages =	{618--629},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-74-3},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{28},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.618},
  URN =		{urn:nbn:de:0030-drops-47265},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014.618},
  annote =	{Keywords: bounded depth circuits, read once branching programs, Santha-Vazirani sources, the coin problem}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2014.692
Space Pseudorandom Generators by Communication Complexity Lower Bounds

Authors: Anat Ganor and Ran Raz

Published in: LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)

Abstract
In 1989, Babai, Nisan and Szegedy gave a construction of a pseudorandom generator for logspace, based on lower bounds for multiparty communication complexity. The seed length of their pseudorandom generator was relatively large, because the best lower bounds for multiparty communication complexity are relatively weak. Subsequently, pseudorandom generators for logspace with seed length O(log^2 n) were given by Nisan, and Impagliazzo, Nisan and Wigderson. In this paper, we show how to use the pseudorandom generator construction of Babai, Nisan and Szegedy to obtain a third construction of a pseudorandom generator with seed length O(log^2 n), achieving the same parameters as Nisan, and Impagliazzo, Nisan and Wigderson. We achieve this by concentrating on protocols in a restricted model of multiparty communication complexity that we call the conservative one-way unicast model and is based on the conservative one-way model of Damm, Jukna and Sgall. We observe that bounds in the conservative one-way unicast model (rather than the standard Number On the Forehead model) are sufficient for the pseudorandom generator construction of Babai, Nisan and Szegedy to work. Roughly speaking, in a conservative one-way unicast communication protocol, the players speak in turns, one after the other in a fixed order, and every message is visible only to the next player. Moreover, before the beginning of the protocol, each player only knows the inputs of the players that speak after she does and a certain function of the inputs of the players that speak before she does. We prove a lower bound for the communication complexity of conservative one-way unicast communication protocols that compute a family of functions obtained by compositions of strong extractors. Our final pseudorandom generator construction is related to, but different from the constructions of Nisan, and Impagliazzo, Nisan and Wigderson.
Cite as

Anat Ganor and Ran Raz. Space Pseudorandom Generators by Communication Complexity Lower Bounds. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 692-703, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{ganor_et_al:LIPIcs.APPROX-RANDOM.2014.692,
  author =	{Ganor, Anat and Raz, Ran},
  title =	{{Space Pseudorandom Generators by Communication Complexity Lower Bounds}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  pages =	{692--703},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-74-3},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{28},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.692},
  URN =		{urn:nbn:de:0030-drops-47324},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014.692},
  annote =	{Keywords: Communication complexity, Logspace, Pseudorandom generator}
}
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