Search Results

Documents authored by Haviv, Ishay

Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2024.35
Testing Intersectingness of Uniform Families

Authors: Ishay Haviv and Michal Parnas

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

Abstract
A set family F is called intersecting if every two members of F intersect, and it is called uniform if all members of F share a common size. A uniform family F ⊆ binom([n],k) of k-subsets of [n] is ε-far from intersecting if one has to remove more than ε ⋅ binom(n,k) of the sets of F to make it intersecting. We study the property testing problem that given query access to a uniform family F ⊆ binom([n],k), asks to distinguish between the case that F is intersecting and the case that it is ε-far from intersecting. We prove that for every fixed integer r, the problem admits a non-adaptive two-sided error tester with query complexity O((ln n)/ε) for ε ≥ Ω((k/n)^r) and a non-adaptive one-sided error tester with query complexity O((ln k)/ε) for ε ≥ Ω((k²/n)^r). The query complexities are optimal up to the logarithmic terms. For ε ≥ Ω((k²/n)²), we further provide a non-adaptive one-sided error tester with optimal query complexity of O(1/ε). Our findings show that the query complexity of the problem behaves differently from that of testing intersectingness of non-uniform families, studied recently by Chen, De, Li, Nadimpalli, and Servedio (ITCS, 2024).
Cite as

Ishay Haviv and Michal Parnas. Testing Intersectingness of Uniform Families. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 35:1-35:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{haviv_et_al:LIPIcs.APPROX/RANDOM.2024.35,
  author =	{Haviv, Ishay and Parnas, Michal},
  title =	{{Testing Intersectingness of Uniform Families}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)},
  pages =	{35:1--35:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-348-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{317},
  editor =	{Kumar, Amit and Ron-Zewi, Noga},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.35},
  URN =		{urn:nbn:de:0030-drops-210288},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2024.35},
  annote =	{Keywords: Intersecting family, Uniform family, Property testing}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2024.39
Nearly Orthogonal Sets over Finite Fields

Authors: Dror Chawin and Ishay Haviv

Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)

Abstract
For a field 𝔽 and integers d and k, a set of vectors of 𝔽^d is called k-nearly orthogonal if its members are non-self-orthogonal and every k+1 of them include an orthogonal pair. We prove that for every prime p there exists a positive constant δ = δ (p), such that for every field 𝔽 of characteristic p and for all integers k ≥ 2 and d ≥ k^{1/(p-1)}, there exists a k-nearly orthogonal set of at least d^{δ ⋅ k^{1/(p-1)} / log k} vectors of 𝔽^d. In particular, for the binary field we obtain a set of d^Ω(k/log k) vectors, and this is tight up to the log k term in the exponent. For comparison, the best known lower bound over the reals is d^Ω(log k / log log k)} (Alon and Szegedy, Graphs and Combin., 1999). The proof combines probabilistic and spectral arguments.
Cite as

Dror Chawin and Ishay Haviv. Nearly Orthogonal Sets over Finite Fields. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 39:1-39:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{chawin_et_al:LIPIcs.SoCG.2024.39,
  author =	{Chawin, Dror and Haviv, Ishay},
  title =	{{Nearly Orthogonal Sets over Finite Fields}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{39:1--39:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-316-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{293},
  editor =	{Mulzer, Wolfgang and Phillips, Jeff M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.39},
  URN =		{urn:nbn:de:0030-drops-199848},
  doi =		{10.4230/LIPIcs.SoCG.2024.39},
  annote =	{Keywords: Nearly orthogonal sets, Finite fields}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2024.60
The Chromatic Number of Kneser Hypergraphs via Consensus Division

Authors: Ishay Haviv

Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)

Abstract
We show that the Consensus Division theorem implies lower bounds on the chromatic number of Kneser hypergraphs, offering a novel proof for a result of Alon, Frankl, and Lovász (Trans. Amer. Math. Soc., 1986) and for its generalization by Kriz (Trans. Amer. Math. Soc., 1992). Our approach is applied to study the computational complexity of the total search problem Kneser^p, which given a succinct representation of a coloring of a p-uniform Kneser hypergraph with fewer colors than its chromatic number, asks to find a monochromatic hyperedge. We prove that for every prime p, the Kneser^p problem with an extended access to the input coloring is efficiently reducible to a quite weak approximation of the Consensus Division problem with p shares. In particular, for p = 2, the problem is efficiently reducible to any non-trivial approximation of the Consensus Halving problem on normalized monotone functions. We further show that for every prime p, the Kneser^p problem lies in the complexity class PPA-p. As an application, we establish limitations on the complexity of the Kneser^p problem, restricted to colorings with a bounded number of colors.
Cite as

Ishay Haviv. The Chromatic Number of Kneser Hypergraphs via Consensus Division. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 60:1-60:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{haviv:LIPIcs.ITCS.2024.60,
  author =	{Haviv, Ishay},
  title =	{{The Chromatic Number of Kneser Hypergraphs via Consensus Division}},
  booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
  pages =	{60:1--60:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-309-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{287},
  editor =	{Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.60},
  URN =		{urn:nbn:de:0030-drops-195883},
  doi =		{10.4230/LIPIcs.ITCS.2024.60},
  annote =	{Keywords: Kneser hypergraphs, consensus division, the complexity classes PPA-p}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2023.73
On Finding Constrained Independent Sets in Cycles

Authors: Ishay Haviv

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

Abstract
A subset of [n] = {1,2,…,n} is called stable if it forms an independent set in the cycle on the vertex set [n]. In 1978, Schrijver proved via a topological argument that for all integers n and k with n ≥ 2k, the family of stable k-subsets of [n] cannot be covered by n-2k+1 intersecting families. We study two total search problems whose totality relies on this result. In the first problem, denoted by Schrijver(n,k,m), we are given an access to a coloring of the stable k-subsets of [n] with m = m(n,k) colors, where m ≤ n-2k+1, and the goal is to find a pair of disjoint subsets that are assigned the same color. While for m = n-2k+1 the problem is known to be PPA-complete, we prove that for m < d ⋅ ⌊n/(2k+d-2)⌋, with d being any fixed constant, the problem admits an efficient algorithm. For m = ⌊n/2⌋-2k+1, we prove that the problem is efficiently reducible to the Kneser problem. Motivated by the relation between the problems, we investigate the family of unstable k-subsets of [n], which might be of independent interest. In the second problem, called Unfair Independent Set in Cycle, we are given 𝓁 subsets V_1, …, V_𝓁 of [n], where 𝓁 ≤ n-2k+1 and |V_i| ≥ 2 for all i ∈ [𝓁], and the goal is to find a stable k-subset S of [n] satisfying the constraints |S ∩ V_i| ≤ |V_i|/2 for i ∈ [𝓁]. We prove that the problem is PPA-complete and that its restriction to instances with n = 3k is at least as hard as the Cycle plus Triangles problem, for which no efficient algorithm is known. On the contrary, we prove that there exists a constant c for which the restriction of the problem to instances with n ≥ c ⋅ k can be solved in polynomial time.
Cite as

Ishay Haviv. On Finding Constrained Independent Sets in Cycles. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 73:1-73:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{haviv:LIPIcs.ICALP.2023.73,
  author =	{Haviv, Ishay},
  title =	{{On Finding Constrained Independent Sets in Cycles}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{73:1--73:16},
  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.73},
  URN =		{urn:nbn:de:0030-drops-181254},
  doi =		{10.4230/LIPIcs.ICALP.2023.73},
  annote =	{Keywords: Schrijver graph, Kneser graph, Stable sets, PPA-completeness}
}
Document
DOI: 10.4230/LIPIcs.STACS.2023.20
Improved NP-Hardness of Approximation for Orthogonality Dimension and Minrank

Authors: Dror Chawin and Ishay Haviv

Published in: LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)

Abstract
The orthogonality dimension of a graph G over ℝ is the smallest integer k for which one can assign a nonzero k-dimensional real vector to each vertex of G, such that every two adjacent vertices receive orthogonal vectors. We prove that for every sufficiently large integer k, it is NP-hard to decide whether the orthogonality dimension of a given graph over ℝ is at most k or at least 2^{(1-o(1))⋅k/2}. We further prove such hardness results for the orthogonality dimension over finite fields as well as for the closely related minrank parameter, which is motivated by the index coding problem in information theory. This in particular implies that it is NP-hard to approximate these graph quantities to within any constant factor. Previously, the hardness of approximation was known to hold either assuming certain variants of the Unique Games Conjecture or for approximation factors smaller than 3/2. The proofs involve the concept of line digraphs and bounds on their orthogonality dimension and on the minrank of their complement.
Cite as

Dror Chawin and Ishay Haviv. Improved NP-Hardness of Approximation for Orthogonality Dimension and Minrank. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 20:1-20:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{chawin_et_al:LIPIcs.STACS.2023.20,
  author =	{Chawin, Dror and Haviv, Ishay},
  title =	{{Improved NP-Hardness of Approximation for Orthogonality Dimension and Minrank}},
  booktitle =	{40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)},
  pages =	{20:1--20:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-266-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{254},
  editor =	{Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.20},
  URN =		{urn:nbn:de:0030-drops-176724},
  doi =		{10.4230/LIPIcs.STACS.2023.20},
  annote =	{Keywords: hardness of approximation, graph coloring, orthogonality dimension, minrank, index coding}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2022.16
A Fixed-Parameter Algorithm for the Schrijver Problem

Authors: Ishay Haviv

Published in: LIPIcs, Volume 249, 17th International Symposium on Parameterized and Exact Computation (IPEC 2022)

Abstract
The Schrijver graph S(n,k) is defined for integers n and k with n ≥ 2k as the graph whose vertices are all the k-subsets of {1,2,…,n} that do not include two consecutive elements modulo n, where two such sets are adjacent if they are disjoint. A result of Schrijver asserts that the chromatic number of S(n,k) is n-2k+2 (Nieuw Arch. Wiskd., 1978). In the computational Schrijver problem, we are given an access to a coloring of the vertices of S(n,k) with n-2k+1 colors, and the goal is to find a monochromatic edge. The Schrijver problem is known to be complete in the complexity class PPA. We prove that it can be solved by a randomized algorithm with running time n^O(1) ⋅ k^O(k), hence it is fixed-parameter tractable with respect to the parameter k.
Cite as

Ishay Haviv. A Fixed-Parameter Algorithm for the Schrijver Problem. In 17th International Symposium on Parameterized and Exact Computation (IPEC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 249, pp. 16:1-16:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{haviv:LIPIcs.IPEC.2022.16,
  author =	{Haviv, Ishay},
  title =	{{A Fixed-Parameter Algorithm for the Schrijver Problem}},
  booktitle =	{17th International Symposium on Parameterized and Exact Computation (IPEC 2022)},
  pages =	{16:1--16:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-260-0},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{249},
  editor =	{Dell, Holger and Nederlof, Jesper},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2022.16},
  URN =		{urn:nbn:de:0030-drops-173721},
  doi =		{10.4230/LIPIcs.IPEC.2022.16},
  annote =	{Keywords: Schrijver graph, Kneser graph, Fixed-parameter tractability}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2022.56
On the Binary and Boolean Rank of Regular Matrices

Authors: Ishay Haviv and Michal Parnas

Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)

Abstract
A 0,1 matrix is said to be regular if all of its rows and columns have the same number of ones. We prove that for infinitely many integers k, there exists a square regular 0,1 matrix with binary rank k, such that the Boolean rank of its complement is k^Ω̃(log k). Equivalently, the ones in the matrix can be partitioned into k combinatorial rectangles, whereas the number of rectangles needed for any cover of its zeros is k^Ω̃(log k). This settles, in a strong form, a question of Pullman (Linear Algebra Appl., 1988) and a conjecture of Hefner, Henson, Lundgren, and Maybee (Congr. Numer., 1990). The result can be viewed as a regular analogue of a recent result of Balodis, Ben-David, Göös, Jain, and Kothari (FOCS, 2021), motivated by the clique vs. independent set problem in communication complexity and by the (disproved) Alon-Saks-Seymour conjecture in graph theory. As an application of the produced regular matrices, we obtain regular counterexamples to the Alon-Saks-Seymour conjecture and prove that for infinitely many integers k, there exists a regular graph with biclique partition number k and chromatic number k^Ω̃(log k).
Cite as

Ishay Haviv and Michal Parnas. On the Binary and Boolean Rank of Regular Matrices. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 56:1-56:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{haviv_et_al:LIPIcs.MFCS.2022.56,
  author =	{Haviv, Ishay and Parnas, Michal},
  title =	{{On the Binary and Boolean Rank of Regular Matrices}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{56:1--56:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-256-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{241},
  editor =	{Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.56},
  URN =		{urn:nbn:de:0030-drops-168545},
  doi =		{10.4230/LIPIcs.MFCS.2022.56},
  annote =	{Keywords: Binary rank, Boolean rank, Regular matrices, Non-deterministic communication complexity, Biclique partition number, Chromatic number}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2022.72
A Fixed-Parameter Algorithm for the Kneser Problem

Authors: Ishay Haviv

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Abstract
The Kneser graph K(n,k) is defined for integers n and k with n ≥ 2k as the graph whose vertices are all the k-subsets of {1,2,…,n} where two such sets are adjacent if they are disjoint. A classical result of Lovász asserts that the chromatic number of K(n,k) is n-2k+2. In the computational Kneser problem, we are given an oracle access to a coloring of the vertices of K(n,k) with n-2k+1 colors, and the goal is to find a monochromatic edge. We present a randomized algorithm for the Kneser problem with running time n^O(1) ⋅ k^O(k). This shows that the problem is fixed-parameter tractable with respect to the parameter k. The analysis involves structural results on intersecting families and on induced subgraphs of Kneser graphs. We also study the Agreeable-Set problem of assigning a small subset of a set of m items to a group of 𝓁 agents, so that all agents value the subset at least as much as its complement. As an application of our algorithm for the Kneser problem, we obtain a randomized polynomial-time algorithm for the Agreeable-Set problem for instances that satisfy 𝓁 ≥ m - O({log m}/{log log m}). We further show that the Agreeable-Set problem is at least as hard as a variant of the Kneser problem with an extended access to the input coloring.
Cite as

Ishay Haviv. A Fixed-Parameter Algorithm for the Kneser Problem. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 72:1-72:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{haviv:LIPIcs.ICALP.2022.72,
  author =	{Haviv, Ishay},
  title =	{{A Fixed-Parameter Algorithm for the Kneser Problem}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{72:1--72:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.72},
  URN =		{urn:nbn:de:0030-drops-164139},
  doi =		{10.4230/LIPIcs.ICALP.2022.72},
  annote =	{Keywords: Kneser graph, Fixed-parameter tractability, Agreeable Set}
}
Document
DOI: 10.4230/LIPIcs.CCC.2021.8
The (Generalized) Orthogonality Dimension of (Generalized) Kneser Graphs: Bounds and Applications

Authors: Alexander Golovnev and Ishay Haviv

Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)

Abstract
The orthogonality dimension of a graph G = (V,E) over a field 𝔽 is the smallest integer t for which there exists an assignment of a vector u_v ∈ 𝔽^t with ⟨ u_v,u_v ⟩ ≠ 0 to every vertex v ∈ V, such that ⟨ u_v, u_{v'} ⟩ = 0 whenever v and v' are adjacent vertices in G. The study of the orthogonality dimension of graphs is motivated by various applications in information theory and in theoretical computer science. The contribution of the present work is two-fold. First, we prove that there exists a constant c such that for every sufficiently large integer t, it is NP-hard to decide whether the orthogonality dimension of an input graph over ℝ is at most t or at least 3t/2-c. At the heart of the proof lies a geometric result, which might be of independent interest, on a generalization of the orthogonality dimension parameter for the family of Kneser graphs, analogously to a long-standing conjecture of Stahl (J. Comb. Theo. Ser. B, 1976). Second, we study the smallest possible orthogonality dimension over finite fields of the complement of graphs that do not contain certain fixed subgraphs. In particular, we provide an explicit construction of triangle-free n-vertex graphs whose complement has orthogonality dimension over the binary field at most n^{1-δ} for some constant δ > 0. Our results involve constructions from the family of generalized Kneser graphs and they are motivated by the rigidity approach to circuit lower bounds. We use them to answer a couple of questions raised by Codenotti, Pudlák, and Resta (Theor. Comput. Sci., 2000), and in particular, to disprove their Odd Alternating Cycle Conjecture over every finite field.
Cite as

Alexander Golovnev and Ishay Haviv. The (Generalized) Orthogonality Dimension of (Generalized) Kneser Graphs: Bounds and Applications. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 8:1-8:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{golovnev_et_al:LIPIcs.CCC.2021.8,
  author =	{Golovnev, Alexander and Haviv, Ishay},
  title =	{{The (Generalized) Orthogonality Dimension of (Generalized) Kneser Graphs: Bounds and Applications}},
  booktitle =	{36th Computational Complexity Conference (CCC 2021)},
  pages =	{8:1--8:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-193-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{200},
  editor =	{Kabanets, Valentine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.8},
  URN =		{urn:nbn:de:0030-drops-142829},
  doi =		{10.4230/LIPIcs.CCC.2021.8},
  annote =	{Keywords: Orthogonality dimension, minrank, rigidity, hardness of approximation, circuit complexity, chromatic number, Kneser graphs}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2021.4
The Complexity of Finding Fair Independent Sets in Cycles

Authors: Ishay Haviv

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

Abstract
Let G be a cycle graph and let V₁,…,V_m be a partition of its vertex set into m sets. An independent set S of G is said to fairly represent the partition if |S ∩ V_i| ≥ 1/2⋅|V_i| - 1 for all i ∈ [m]. It is known that for every cycle and every partition of its vertex set, there exists an independent set that fairly represents the partition (Aharoni et al., A Journey through Discrete Math., 2017). We prove that the problem of finding such an independent set is PPA-complete. As an application, we show that the problem of finding a monochromatic edge in a Schrijver graph, given a succinct representation of a coloring that uses fewer colors than its chromatic number, is PPA-complete as well. The work is motivated by the computational aspects of the "cycle plus triangles" problem and of its extensions.
Cite as

Ishay Haviv. The Complexity of Finding Fair Independent Sets in Cycles. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 4:1-4:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{haviv:LIPIcs.ITCS.2021.4,
  author =	{Haviv, Ishay},
  title =	{{The Complexity of Finding Fair Independent Sets in Cycles}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{4:1--4:14},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.4},
  URN =		{urn:nbn:de:0030-drops-135431},
  doi =		{10.4230/LIPIcs.ITCS.2021.4},
  annote =	{Keywords: Fair independent sets in cycles, the complexity class \{PPA\}, Schrijver graphs}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2019.39
Approximating the Orthogonality Dimension of Graphs and Hypergraphs

Authors: Ishay Haviv

Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)

Abstract
A t-dimensional orthogonal representation of a hypergraph is an assignment of nonzero vectors in R^t to its vertices, such that every hyperedge contains two vertices whose vectors are orthogonal. The orthogonality dimension of a hypergraph H, denoted by overline{xi}(H), is the smallest integer t for which there exists a t-dimensional orthogonal representation of H. In this paper we study computational aspects of the orthogonality dimension of graphs and hypergraphs. We prove that for every k >= 4, it is NP-hard (resp. quasi-NP-hard) to distinguish n-vertex k-uniform hypergraphs H with overline{xi}(H) <= 2 from those satisfying overline{xi}(H) >= Omega(log^delta n) for some constant delta>0 (resp. overline{xi}(H) >= Omega(log^{1-o(1)} n)). For graphs, we relate the NP-hardness of approximating the orthogonality dimension to a variant of a long-standing conjecture of Stahl. We also consider the algorithmic problem in which given a graph G with overline{xi}(G) <= 3 the goal is to find an orthogonal representation of G of as low dimension as possible, and provide a polynomial time approximation algorithm based on semidefinite programming.
Cite as

Ishay Haviv. Approximating the Orthogonality Dimension of Graphs and Hypergraphs. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 39:1-39:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{haviv:LIPIcs.MFCS.2019.39,
  author =	{Haviv, Ishay},
  title =	{{Approximating the Orthogonality Dimension of Graphs and Hypergraphs}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{39:1--39:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.39},
  URN =		{urn:nbn:de:0030-drops-109836},
  doi =		{10.4230/LIPIcs.MFCS.2019.39},
  annote =	{Keywords: orthogonal representations of hypergraphs, orthogonality dimension, hardness of approximation, Kneser and Schrijver graphs, semidefinite programming}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2018.13
On Minrank and the Lovász Theta Function

Authors: Ishay Haviv

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

Abstract
Two classical upper bounds on the Shannon capacity of graphs are the theta-function due to Lovász and the minrank parameter due to Haemers. We provide several explicit constructions of n-vertex graphs with a constant theta-function and minrank at least n^delta for a constant delta>0 (over various prime order fields). This implies a limitation on the theta-function-based algorithmic approach to approximating the minrank parameter of graphs. The proofs involve linear spaces of multivariate polynomials and the method of higher incidence matrices.
Cite as

Ishay Haviv. On Minrank and the Lovász Theta Function. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 13:1-13:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{haviv:LIPIcs.APPROX-RANDOM.2018.13,
  author =	{Haviv, Ishay},
  title =	{{On Minrank and the Lov\'{a}sz Theta Function}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)},
  pages =	{13:1--13:15},
  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.13},
  URN =		{urn:nbn:de:0030-drops-94170},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2018.13},
  annote =	{Keywords: Minrank, Theta Function, Shannon capacity, Multivariate polynomials, Higher incidence matrices}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2018.42
On Minrank and Forbidden Subgraphs

Authors: Ishay Haviv

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

Abstract
The minrank over a field F of a graph G on the vertex set {1,2,...,n} is the minimum possible rank of a matrix M in F^{n x n} such that M_{i,i} != 0 for every i, and M_{i,j}=0 for every distinct non-adjacent vertices i and j in G. For an integer n, a graph H, and a field F, let g(n,H,F) denote the maximum possible minrank over F of an n-vertex graph whose complement contains no copy of H. In this paper we study this quantity for various graphs H and fields F. For finite fields, we prove by a probabilistic argument a general lower bound on g(n,H,F), which yields a nearly tight bound of Omega(sqrt{n}/log n) for the triangle H=K_3. For the real field, we prove by an explicit construction that for every non-bipartite graph H, g(n,H,R) >= n^delta for some delta = delta(H)>0. As a by-product of this construction, we disprove a conjecture of Codenotti, Pudlák, and Resta. The results are motivated by questions in information theory, circuit complexity, and geometry.
Cite as

Ishay Haviv. On Minrank and Forbidden Subgraphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 42:1-42:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{haviv:LIPIcs.APPROX-RANDOM.2018.42,
  author =	{Haviv, Ishay},
  title =	{{On Minrank and Forbidden Subgraphs}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)},
  pages =	{42:1--42:14},
  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.42},
  URN =		{urn:nbn:de:0030-drops-94461},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2018.42},
  annote =	{Keywords: Minrank, Forbidden subgraphs, Shannon capacity, Circuit Complexity}
}
Document
DOI: 10.4230/LIPIcs.CCC.2015.58
The List-Decoding Size of Fourier-Sparse Boolean Functions

Authors: Ishay Haviv and Oded Regev

Published in: LIPIcs, Volume 33, 30th Conference on Computational Complexity (CCC 2015)

Abstract
A function defined on the Boolean hypercube is k-Fourier-sparse if it has at most k nonzero Fourier coefficients. For a function f: F_2^n -> R and parameters k and d, we prove a strong upper bound on the number of k-Fourier-sparse Boolean functions that disagree with f on at most d inputs. Our bound implies that the number of uniform and independent random samples needed for learning the class of k-Fourier-sparse Boolean functions on n variables exactly is at most O(n * k * log(k)). As an application, we prove an upper bound on the query complexity of testing Booleanity of Fourier-sparse functions. Our bound is tight up to a logarithmic factor and quadratically improves on a result due to Gur and Tamuz [Chicago J. Theor. Comput. Sci.,2013].
Cite as

Ishay Haviv and Oded Regev. The List-Decoding Size of Fourier-Sparse Boolean Functions. In 30th Conference on Computational Complexity (CCC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 33, pp. 58-71, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{haviv_et_al:LIPIcs.CCC.2015.58,
  author =	{Haviv, Ishay and Regev, Oded},
  title =	{{The List-Decoding Size of Fourier-Sparse Boolean Functions}},
  booktitle =	{30th Conference on Computational Complexity (CCC 2015)},
  pages =	{58--71},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-81-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{33},
  editor =	{Zuckerman, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2015.58},
  URN =		{urn:nbn:de:0030-drops-50600},
  doi =		{10.4230/LIPIcs.CCC.2015.58},
  annote =	{Keywords: Fourier-sparse functions, list-decoding, learning theory, property testing}
}
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 Imprint Privacy Contact