10 Search Results for "Moran, Shay"


Document
RANDOM
Lower Bound Methods for Sign-Rank and Their Limitations

Authors: Hamed Hatami, Pooya Hatami, William Pires, Ran Tao, and Rosie Zhao

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


Abstract
The sign-rank of a matrix A with ±1 entries is the smallest rank of a real matrix with the same sign pattern as A. To the best of our knowledge, there are only three known methods for proving lower bounds on the sign-rank of explicit matrices: (i) Sign-rank is at least the VC-dimension; (ii) Forster’s method, which states that sign-rank is at least the inverse of the largest possible average margin among the representations of the matrix by points and half-spaces; (iii) Sign-rank is at least a logarithmic function of the density of the largest monochromatic rectangle. We prove several results regarding the limitations of these methods. - We prove that, qualitatively, the monochromatic rectangle density is the strongest of these three lower bounds. If it fails to provide a super-constant lower bound for the sign-rank of a matrix, then the other two methods will fail as well. - We show that there exist n × n matrices with sign-rank n^Ω(1) for which none of these methods can provide a super-constant lower bound. - We show that sign-rank is at most an exponential function of the deterministic communication complexity with access to an equality oracle. We combine this result with Green and Sanders' quantitative version of Cohen’s idempotent theorem to show that for a large class of sign matrices (e.g., xor-lifts), sign-rank is at most an exponential function of the γ₂ norm of the matrix. We conjecture that this holds for all sign matrices. - Towards answering a question of Linial, Mendelson, Schechtman, and Shraibman regarding the relation between sign-rank and discrepancy, we conjecture that sign-ranks of the ±1 adjacency matrices of hypercube graphs can be arbitrarily large. We prove that none of the three lower bound techniques can resolve this conjecture in the affirmative.

Cite as

Hamed Hatami, Pooya Hatami, William Pires, Ran Tao, and Rosie Zhao. Lower Bound Methods for Sign-Rank and Their Limitations. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 22:1-22:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{hatami_et_al:LIPIcs.APPROX/RANDOM.2022.22,
  author =	{Hatami, Hamed and Hatami, Pooya and Pires, William and Tao, Ran and Zhao, Rosie},
  title =	{{Lower Bound Methods for Sign-Rank and Their Limitations}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)},
  pages =	{22:1--22:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-249-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{245},
  editor =	{Chakrabarti, Amit and Swamy, Chaitanya},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.22},
  URN =		{urn:nbn:de:0030-drops-171445},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2022.22},
  annote =	{Keywords: Average Margin, Communication complexity, margin complexity, monochromatic rectangle, Sign-rank, Unbounded-error communication complexity, VC-dimension}
}
Document
Uniform Brackets, Containers, and Combinatorial Macbeath Regions

Authors: Kunal Dutta, Arijit Ghosh, and Shay Moran

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)


Abstract
We study the connections between three seemingly different combinatorial structures - uniform brackets in statistics and probability theory, containers in online and distributed learning theory, and combinatorial Macbeath regions, or Mnets in discrete and computational geometry. We show that these three concepts are manifestations of a single combinatorial property that can be expressed under a unified framework along the lines of Vapnik-Chervonenkis type theory for uniform convergence. These new connections help us to bring tools from discrete and computational geometry to prove improved bounds for these objects. Our improved bounds help to get an optimal algorithm for distributed learning of halfspaces, an improved algorithm for the distributed convex set disjointness problem, and improved regret bounds for online algorithms against σ-smoothed adversary for a large class of semi-algebraic threshold functions.

Cite as

Kunal Dutta, Arijit Ghosh, and Shay Moran. Uniform Brackets, Containers, and Combinatorial Macbeath Regions. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 59:1-59:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{dutta_et_al:LIPIcs.ITCS.2022.59,
  author =	{Dutta, Kunal and Ghosh, Arijit and Moran, Shay},
  title =	{{Uniform Brackets, Containers, and Combinatorial Macbeath Regions}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{59:1--59:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.59},
  URN =		{urn:nbn:de:0030-drops-156551},
  doi =		{10.4230/LIPIcs.ITCS.2022.59},
  annote =	{Keywords: communication complexity, distributed learning, emperical process theory, online algorithms, discrete geometry, computational geometry}
}
Document
The Entropy of Lies: Playing Twenty Questions with a Liar

Authors: Yuval Dagan, Yuval Filmus, Daniel Kane, and Shay Moran

Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)


Abstract
"Twenty questions" is a guessing game played by two players: Bob thinks of an integer between 1 and n, and Alice’s goal is to recover it using a minimal number of Yes/No questions. Shannon’s entropy has a natural interpretation in this context. It characterizes the average number of questions used by an optimal strategy in the distributional variant of the game: let μ be a distribution over [n], then the average number of questions used by an optimal strategy that recovers x∼ μ is between H(μ) and H(μ)+1. We consider an extension of this game where at most k questions can be answered falsely. We extend the classical result by showing that an optimal strategy uses roughly H(μ) + k H_2(μ) questions, where H_2(μ) = ∑_x μ(x)log log 1/μ(x). This also generalizes a result by Rivest et al. (1980) for the uniform distribution. Moreover, we design near optimal strategies that only use comparison queries of the form "x ≤ c?" for c ∈ [n]. The usage of comparison queries lends itself naturally to the context of sorting, where we derive sorting algorithms in the presence of adversarial noise.

Cite as

Yuval Dagan, Yuval Filmus, Daniel Kane, and Shay Moran. The Entropy of Lies: Playing Twenty Questions with a Liar. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 1:1-1:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{dagan_et_al:LIPIcs.ITCS.2021.1,
  author =	{Dagan, Yuval and Filmus, Yuval and Kane, Daniel and Moran, Shay},
  title =	{{The Entropy of Lies: Playing Twenty Questions with a Liar}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{1:1--1:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-177-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{185},
  editor =	{Lee, James R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.1},
  URN =		{urn:nbn:de:0030-drops-135400},
  doi =		{10.4230/LIPIcs.ITCS.2021.1},
  annote =	{Keywords: entropy, twenty questions, algorithms, sorting}
}
Document
Singularly Optimal Randomized Leader Election

Authors: Shay Kutten, William K. Moses Jr., Gopal Pandurangan, and David Peleg

Published in: LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020)


Abstract
This paper concerns designing distributed algorithms that are singularly optimal, i.e., algorithms that are simultaneously time and message optimal, for the fundamental leader election problem in networks. Our main result is a randomized distributed leader election algorithm for asynchronous complete networks that is essentially (up to a polylogarithmic factor) singularly optimal. Our algorithm uses O(n) messages with high probability and runs in O(log² n) time (with high probability) to elect a unique leader. The O(n) message complexity should be contrasted with the Ω(n log n) lower bounds for the deterministic message complexity of leader election algorithms (regardless of time), proven by Korach, Moran, and Zaks (TCS, 1989) for asynchronous algorithms and by Afek and Gafni (SIAM J. Comput., 1991) for synchronous networks. Hence, our result also separates the message complexities of randomized and deterministic leader election. More importantly, our (randomized) time complexity of O(log² n) for obtaining the optimal O(n) message complexity is significantly smaller than the long-standing Θ̃(n) time complexity obtained by Afek and Gafni and by Singh (SIAM J. Comput., 1997) for message optimal (deterministic) election in asynchronous networks. Afek and Gafni also conjectured that Θ̃(n) time would be optimal for message-optimal asynchronous algorithms. Our result shows that randomized algorithms are significantly faster. Turning to synchronous complete networks, Afek and Gafni showed an essentially singularly optimal deterministic algorithm with O(log n) time and O(n log n) messages. Ramanathan et al. (Distrib. Comput. 2007) used randomization to improve the message complexity, and showed a randomized algorithm with O(n) messages but still with O(log n) time (with failure probability O(1 / log^{Ω(1)}n)). Our second result shows that synchronous complete networks admit a tightly singularly optimal randomized algorithm, with O(1) time and O(n) messages (both bounds are optimal). Moreover, our algorithm’s time bound holds with certainty, and its message bound holds with high probability, i.e., 1-1/n^c for constant c. Our results demonstrate that leader election can be solved in a simultaneously message and time-efficient manner in asynchronous complete networks using randomization. It is open whether this is possible in asynchronous general networks.

Cite as

Shay Kutten, William K. Moses Jr., Gopal Pandurangan, and David Peleg. Singularly Optimal Randomized Leader Election. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 22:1-22:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{kutten_et_al:LIPIcs.DISC.2020.22,
  author =	{Kutten, Shay and Moses Jr., William K. and Pandurangan, Gopal and Peleg, David},
  title =	{{Singularly Optimal Randomized Leader Election}},
  booktitle =	{34th International Symposium on Distributed Computing (DISC 2020)},
  pages =	{22:1--22:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-168-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{179},
  editor =	{Attiya, Hagit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.22},
  URN =		{urn:nbn:de:0030-drops-131002},
  doi =		{10.4230/LIPIcs.DISC.2020.22},
  annote =	{Keywords: Leader election, Asynchronous systems, Randomized algorithms, Singularly optimal, Complete networks}
}
Document
Track A: Algorithms, Complexity and Games
Unlabeled Sample Compression Schemes and Corner Peelings for Ample and Maximum Classes

Authors: Jérémie Chalopin, Victor Chepoi, Shay Moran, and Manfred K. Warmuth

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)


Abstract
We examine connections between combinatorial notions that arise in machine learning and topological notions in cubical/simplicial geometry. These connections enable to export results from geometry to machine learning. Our first main result is based on a geometric construction by H. Tracy Hall (2004) of a partial shelling of the cross-polytope which can not be extended. We use it to derive a maximum class of VC dimension 3 that has no corners. This refutes several previous works in machine learning from the past 11 years. In particular, it implies that the previous constructions of optimal unlabeled compression schemes for maximum classes are erroneous. On the positive side we present a new construction of an optimal unlabeled compression scheme for maximum classes. We leave as open whether our unlabeled compression scheme extends to ample (a.k.a. lopsided or extremal) classes, which represent a natural and far-reaching generalization of maximum classes. Towards resolving this question, we provide a geometric characterization in terms of unique sink orientations of the 1-skeletons of associated cubical complexes.

Cite as

Jérémie Chalopin, Victor Chepoi, Shay Moran, and Manfred K. Warmuth. Unlabeled Sample Compression Schemes and Corner Peelings for Ample and Maximum Classes. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 34:1-34:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{chalopin_et_al:LIPIcs.ICALP.2019.34,
  author =	{Chalopin, J\'{e}r\'{e}mie and Chepoi, Victor and Moran, Shay and Warmuth, Manfred K.},
  title =	{{Unlabeled Sample Compression Schemes and Corner Peelings for Ample and Maximum Classes}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{34:1--34:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.34},
  URN =		{urn:nbn:de:0030-drops-106105},
  doi =		{10.4230/LIPIcs.ICALP.2019.34},
  annote =	{Keywords: VC-dimension, sample compression, Sauer-Shelah-Perles lemma, Sandwich lemma, maximum class, ample/extremal class, corner peeling, unique sink orientation}
}
Document
On Weak epsilon-Nets and the Radon Number

Authors: Shay Moran and Amir Yehudayoff

Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)


Abstract
We show that the Radon number characterizes the existence of weak nets in separable convexity spaces (an abstraction of the Euclidean notion of convexity). The construction of weak nets when the Radon number is finite is based on Helly’s property and on metric properties of VC classes. The lower bound on the size of weak nets when the Radon number is large relies on the chromatic number of the Kneser graph. As an application, we prove an amplification result for weak epsilon-nets.

Cite as

Shay Moran and Amir Yehudayoff. On Weak epsilon-Nets and the Radon Number. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 51:1-51:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{moran_et_al:LIPIcs.SoCG.2019.51,
  author =	{Moran, Shay and Yehudayoff, Amir},
  title =	{{On Weak epsilon-Nets and the Radon Number}},
  booktitle =	{35th International Symposium on Computational Geometry (SoCG 2019)},
  pages =	{51:1--51:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-104-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{129},
  editor =	{Barequet, Gill and Wang, Yusu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.51},
  URN =		{urn:nbn:de:0030-drops-104551},
  doi =		{10.4230/LIPIcs.SoCG.2019.51},
  annote =	{Keywords: abstract convexity, weak epsilon nets, Radon number, VC dimension, Haussler packing lemma, Kneser graphs}
}
Document
Generalized Comparison Trees for Point-Location Problems

Authors: Daniel M. Kane, Shachar Lovett, and Shay Moran

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)


Abstract
Let H be an arbitrary family of hyper-planes in d-dimensions. We show that the point-location problem for H can be solved by a linear decision tree that only uses a special type of queries called generalized comparison queries. These queries correspond to hyperplanes that can be written as a linear combination of two hyperplanes from H; in particular, if all hyperplanes in H are k-sparse then generalized comparisons are 2k-sparse. The depth of the obtained linear decision tree is polynomial in d and logarithmic in |H|, which is comparable to previous results in the literature that use general linear queries. This extends the study of comparison trees from a previous work by the authors [Kane {et al.}, FOCS 2017]. The main benefit is that using generalized comparison queries allows to overcome limitations that apply for the more restricted type of comparison queries. Our analysis combines a seminal result of Forster regarding sets in isotropic position [Forster, JCSS 2002], the margin-based inference dimension analysis for comparison queries from [Kane {et al.}, FOCS 2017], and compactness arguments.

Cite as

Daniel M. Kane, Shachar Lovett, and Shay Moran. Generalized Comparison Trees for Point-Location Problems. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 82:1-82:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{kane_et_al:LIPIcs.ICALP.2018.82,
  author =	{Kane, Daniel M. and Lovett, Shachar and Moran, Shay},
  title =	{{Generalized Comparison Trees for Point-Location Problems}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{82:1--82:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.82},
  URN =		{urn:nbn:de:0030-drops-90862},
  doi =		{10.4230/LIPIcs.ICALP.2018.82},
  annote =	{Keywords: linear decision trees, comparison queries, point location problems}
}
Document
Shattered Sets and the Hilbert Function

Authors: Shay Moran and Cyrus Rashtchian

Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)


Abstract
We study complexity measures on subsets of the boolean hypercube and exhibit connections between algebra (the Hilbert function) and combinatorics (VC theory). These connections yield results in both directions. Our main complexity-theoretic result demonstrates that a large and natural family of linear program feasibility problems cannot be computed by polynomial-sized constant-depth circuits. Moreover, our result applies to a stronger regime in which the hyperplanes are fixed and only the directions of the inequalities are given as input to the circuit. We derive this result by proving that a rich class of extremal functions in VC theory cannot be approximated by low-degree polynomials. We also present applications of algebra to combinatorics. We provide a new algebraic proof of the Sandwich Theorem, which is a generalization of the well-known Sauer-Perles-Shelah Lemma. Finally, we prove a structural result about downward-closed sets, related to the Chvatal conjecture in extremal combinatorics.

Cite as

Shay Moran and Cyrus Rashtchian. Shattered Sets and the Hilbert Function. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 70:1-70:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@InProceedings{moran_et_al:LIPIcs.MFCS.2016.70,
  author =	{Moran, Shay and Rashtchian, Cyrus},
  title =	{{Shattered Sets and the Hilbert Function}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{70:1--70:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.70},
  URN =		{urn:nbn:de:0030-drops-64814},
  doi =		{10.4230/LIPIcs.MFCS.2016.70},
  annote =	{Keywords: VC dimension, shattered sets, sandwich theorem, Hilbert function, polynomial method, linear programming, Chvatal's conjecture, downward-closed sets}
}
Document
Hitting Set for Hypergraphs of Low VC-dimension

Authors: Karl Bringmann, László Kozma, Shay Moran, and N. S. Narayanaswamy

Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)


Abstract
We study the complexity of the Hitting Set problem in set systems (hypergraphs) that avoid certain sub-structures. In particular, we characterize the classical and parameterized complexity of the problem when the Vapnik-Chervonenkis dimension (VC-dimension) of the input is small. VC-dimension is a natural measure of complexity of set systems. Several tractable instances of Hitting Set with a geometric or graph-theoretical flavor are known to have low VC-dimension. In set systems of bounded VC-dimension, Hitting Set is known to admit efficient and almost optimal approximation algorithms (Brönnimann and Goodrich, 1995; Even, Rawitz, and Shahar, 2005; Agarwal and Pan, 2014). In contrast to these approximation-results, a low VC-dimension does not necessarily imply tractability in the parameterized sense. In fact, we show that Hitting Set is W[1]-hard already on inputs with VC-dimension 2, even if the VC-dimension of the dual set system is also 2. Thus, Hitting Set is very unlikely to be fixed-parameter tractable even in this arguably simple case. This answers an open question raised by King in 2010. For set systems whose (primal or dual) VC-dimension is 1, we show that Hitting Set is solvable in polynomial time. To bridge the gap in complexity between the classes of inputs with VC-dimension 1 and 2, we use a measure that is more fine-grained than VC-dimension. In terms of this measure, we identify a sharp threshold where the complexity of Hitting Set transitions from polynomial-time-solvable to NP-hard. The tractable class that lies just under the threshold is a generalization of Edge Cover, and thus extends the domain of polynomial-time tractability of Hitting Set.

Cite as

Karl Bringmann, László Kozma, Shay Moran, and N. S. Narayanaswamy. Hitting Set for Hypergraphs of Low VC-dimension. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 23:1-23:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@InProceedings{bringmann_et_al:LIPIcs.ESA.2016.23,
  author =	{Bringmann, Karl and Kozma, L\'{a}szl\'{o} and Moran, Shay and Narayanaswamy, N. S.},
  title =	{{Hitting Set for Hypergraphs of Low VC-dimension}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{23:1--23:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Sankowski, Piotr and Zaroliagis, Christos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.23},
  URN =		{urn:nbn:de:0030-drops-63749},
  doi =		{10.4230/LIPIcs.ESA.2016.23},
  annote =	{Keywords: hitting set, VC-dimension}
}
Document
Internal Compression of Protocols to Entropy

Authors: Balthazar Bauer, Shay Moran, and Amir Yehudayoff

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


Abstract
We study internal compression of communication protocols to their internal entropy, which is the entropy of the transcript from the players' perspective. We provide two internal compression schemes with error. One of a protocol of Feige et al. for finding the first difference between two strings. The second and main one is an internal compression with error epsilon > 0 of a protocol with internal entropy H^{int} and communication complexity C to a protocol with communication at most order (H^{int}/epsilon)^2 * log(log(C)). This immediately implies a similar compression to the internal information of public-coin protocols, which provides an exponential improvement over previously known public-coin compressions in the dependence on C. It further shows that in a recent protocol of Ganor, Kol and Raz, it is impossible to move the private randomness to be public without an exponential cost. To the best of our knowledge, No such example was previously known.

Cite as

Balthazar Bauer, Shay Moran, and Amir Yehudayoff. Internal Compression of Protocols to Entropy. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 481-496, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{bauer_et_al:LIPIcs.APPROX-RANDOM.2015.481,
  author =	{Bauer, Balthazar and Moran, Shay and Yehudayoff, Amir},
  title =	{{Internal Compression of Protocols to Entropy}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)},
  pages =	{481--496},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-89-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{40},
  editor =	{Garg, Naveen and Jansen, Klaus and Rao, Anup and Rolim, Jos\'{e} D. P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.481},
  URN =		{urn:nbn:de:0030-drops-53198},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2015.481},
  annote =	{Keywords: Communication complexity, Information complexity, Compression, Simulation, Entropy}
}
  • Refine by Author
  • 8 Moran, Shay
  • 2 Yehudayoff, Amir
  • 1 Bauer, Balthazar
  • 1 Bringmann, Karl
  • 1 Chalopin, Jérémie
  • Show More...

  • Refine by Classification
  • 3 Theory of computation
  • 2 Theory of computation → Computational geometry
  • 1 Mathematics of computing → Combinatoric problems
  • 1 Mathematics of computing → Combinatorics
  • 1 Mathematics of computing → Discrete mathematics
  • Show More...

  • Refine by Keyword
  • 3 VC-dimension
  • 2 Communication complexity
  • 2 VC dimension
  • 1 Asynchronous systems
  • 1 Average Margin
  • Show More...

  • Refine by Type
  • 10 document

  • Refine by Publication Year
  • 2 2016
  • 2 2019
  • 2 2022
  • 1 2015
  • 1 2018
  • Show More...

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