DROPS

Document

DOI: 10.4230/LIPIcs.ITCS.2026.104

Dimension-Free Correlated Sampling for the Hypersimplex

Authors: Joseph (Seffi) Naor, Nitya Raju, Abhishek Shetty, Aravind Srinivasan, Renata Valieva, and David Wajc

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract

Sampling from multiple distributions so as to maximize overlap has been studied by statisticians since the 1950s. Since the 2000s, such correlated sampling from the probability simplex has been a powerful building block in disparate areas of theoretical computer science. We study a generalization of this problem to sampling sets from given vectors in the hypersimplex, i.e., outputting sets of size (at most) k ∈ [n], while maximizing the overlap of the sampled sets. Specifically, the expected difference between two output sets should be at most α times their input vectors' 𝓁₁ distance. A value of α = O(log n) is known to be achievable, due to Chen et al. (ICALP'17). We improve this factor to O(log k), independent of the ambient dimension n. Our algorithm satisfies other desirable properties, including (up to a log^* n factor) input-sparsity sampling time, logarithmic parallel depth and dynamic update time, as well as preservation of submodular objectives. Anticipating broader use of correlated sampling algorithms for the hypersimplex, we present applications of our algorithm to online paging, offline approximation of metric multi-labeling, and swift multi-scenario submodular welfare approximating reallocation.

Cite as

Joseph (Seffi) Naor, Nitya Raju, Abhishek Shetty, Aravind Srinivasan, Renata Valieva, and David Wajc. Dimension-Free Correlated Sampling for the Hypersimplex. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 104:1-104:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{naor_et_al:LIPIcs.ITCS.2026.104,
  author =	{Naor, Joseph (Seffi) and Raju, Nitya and Shetty, Abhishek and Srinivasan, Aravind and Valieva, Renata and Wajc, David},
  title =	{{Dimension-Free Correlated Sampling for the Hypersimplex}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{104:1--104:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  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.ITCS.2026.104},
  URN =		{urn:nbn:de:0030-drops-253918},
  doi =		{10.4230/LIPIcs.ITCS.2026.104},
  annote =	{Keywords: Correlated Rounding, Dependent Rounding}
}

Document

DOI: 10.4230/LIPIcs.ITCS.2026.52

Diffie-Hellman Key Exchange from Commutativity to Group Laws

Authors: Dung Hoang Duong, Youming Qiao, and Chuanqi Zhang

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract

In Diffie-Hellman key exchange, the commutativity of power operations is instrumental in the agreement of keys. Viewing commutativity as a law in abelian groups, we propose Diffie-Hellman key exchange in the group action framework (Brassard-Yung, Crypto'90; Ji-Qiao-Song-Yun, TCC'19), for actions of non-abelian groups with laws. The security of this protocol is shown, following Fischlin, Günther, Schmidt, and Warinschi (IEEE S&P'16), based on a pseudorandom group action assumption. A concrete instantiation is proposed based on the monomial code equivalence problem.

Cite as

Dung Hoang Duong, Youming Qiao, and Chuanqi Zhang. Diffie-Hellman Key Exchange from Commutativity to Group Laws. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 52:1-52:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{duong_et_al:LIPIcs.ITCS.2026.52,
  author =	{Duong, Dung Hoang and Qiao, Youming and Zhang, Chuanqi},
  title =	{{Diffie-Hellman Key Exchange from Commutativity to Group Laws}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{52:1--52:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  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.ITCS.2026.52},
  URN =		{urn:nbn:de:0030-drops-253396},
  doi =		{10.4230/LIPIcs.ITCS.2026.52},
  annote =	{Keywords: Diffie-Hellman, Key Exchange, Group Laws, Group Actions, Code Equivalence}
}

Document

DOI: 10.4230/LIPIcs.IPEC.2025.5

Kernelization for H-Coloring

Authors: Yael Berkman and Ishay Haviv

Published in: LIPIcs, Volume 358, 20th International Symposium on Parameterized and Exact Computation (IPEC 2025)

Abstract

For a fixed graph H, the H-Coloring problem asks whether a given graph admits an edge-preserving function from its vertex set to that of H. A seminal theorem of Hell and Nešetřil asserts that the H-Coloring problem is NP-hard whenever H is loopless and non-bipartite. A result of Jansen and Pieterse implies that for every graph H, the H-Coloring problem parameterized by the vertex cover number k admits a kernel with O(k^Δ(H)) vertices and bit-size bounded by O(k^Δ(H)⋅log k), where Δ(H) denotes the maximum degree in H. For the case where H is a complete graph on at least three vertices, this kernel size nearly matches conditional lower bounds established by Jansen and Kratsch and by Jansen and Pieterse. This paper presents new upper and lower bounds on the kernel size of H-Coloring problems parameterized by the vertex cover number. The upper bounds arise from two kernelization algorithms. The first is purely combinatorial, and its size is governed by a structural quantity of the graph H, called the non-adjacency witness number. As applications, we obtain kernels whose size is bounded by a fixed polynomial for natural classes of graphs H with unbounded maximum degree, such as planar graphs and, more broadly, graphs with bounded degeneracy. More strikingly, we show that for almost every graph H, the degree of the polynomial that bounds the size of our combinatorial kernel grows only logarithmically in Δ(H). Our second kernel leverages linear-algebraic tools and involves the notion of faithful independent representations of graphs. It strengthens the general bound from prior work and, among other applications, yields near-optimal kernels for problems concerning the dimension of orthogonal graph representations over finite fields. We complement our kernelization results with conditional lower bounds, thereby nearly settling the kernel complexity of the problem for various target graphs H.

Cite as

Yael Berkman and Ishay Haviv. Kernelization for H-Coloring. In 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 358, pp. 5:1-5:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{berkman_et_al:LIPIcs.IPEC.2025.5,
  author =	{Berkman, Yael and Haviv, Ishay},
  title =	{{Kernelization for H-Coloring}},
  booktitle =	{20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
  pages =	{5:1--5:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-407-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{358},
  editor =	{Agrawal, Akanksha and van Leeuwen, Erik Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2025.5},
  URN =		{urn:nbn:de:0030-drops-251376},
  doi =		{10.4230/LIPIcs.IPEC.2025.5},
  annote =	{Keywords: Kernelization, Graph coloring, Graph homomorphism}
}

Document

DOI: 10.4230/LIPIcs.MFCS.2025.37

New Hardness Results for Low-Rank Matrix Completion

Authors: Dror Chawin and Ishay Haviv

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract

The low-rank matrix completion problem asks whether a given real matrix with missing values can be completed so that the resulting matrix has low rank or is close to a low-rank matrix. The completed matrix is often required to satisfy additional structural constraints, such as positive semi-definiteness or a bounded infinity norm. The problem arises in various research fields, including machine learning, statistics, and theoretical computer science, and has broad real-world applications. This paper presents new NP-hardness results for low-rank matrix completion problems. We show that for every sufficiently large integer d and any real number ε ∈ [2^{-O(d)},1/7], given a partial matrix A with exposed values of magnitude at most 1 that admits a positive semi-definite completion of rank d, it is NP-hard to find a positive semi-definite matrix that agrees with each given value of A up to an additive error of at most ε, even when the rank is allowed to exceed d by a multiplicative factor of O (1/(ε²⋅log(1/ε))). This strengthens a result of Hardt, Meka, Raghavendra, and Weitz (COLT, 2014), which applies to multiplicative factors smaller than 2 and to ε that decays polynomially in d. We establish similar NP-hardness results for the case where the completed matrix is constrained to have a bounded infinity norm (rather than be positive semi-definite), for which all previous hardness results rely on complexity assumptions related to the Unique Games Conjecture. Our proofs involve a novel notion of nearly orthonormal representations of graphs, the concept of line digraphs, and bounds on the rank of perturbed identity matrices.

Cite as

Dror Chawin and Ishay Haviv. New Hardness Results for Low-Rank Matrix Completion. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 37:1-37:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chawin_et_al:LIPIcs.MFCS.2025.37,
  author =	{Chawin, Dror and Haviv, Ishay},
  title =	{{New Hardness Results for Low-Rank Matrix Completion}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{37:1--37:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.37},
  URN =		{urn:nbn:de:0030-drops-241448},
  doi =		{10.4230/LIPIcs.MFCS.2025.37},
  annote =	{Keywords: hardness of approximation, low-rank matrix completion, graph coloring}
}

Document

DOI: 10.4230/LIPIcs.SEA.2025.18

Engineering Insights into Biclique Partitions and Fractional Binary Ranks of Matrices

Authors: Angikar Ghosal and Andreas Karrenbauer

Published in: LIPIcs, Volume 338, 23rd International Symposium on Experimental Algorithms (SEA 2025)

Abstract

We investigate structural properties of the binary rank of Kronecker powers of binary matrices, equivalently, the biclique partition numbers of the corresponding bipartite graphs. To this end, we engineer a Column Generation approach to solve linear optimization problems for the fractional biclique partition number of bipartite graphs, specifically examining the Domino graph and its Kronecker powers. We address the challenges posed by the double exponential growth of the number of bicliques in increasing Kronecker powers. We discuss various strategies to generate suitable initial sets of bicliques, including an inductive method for increasing Kronecker powers. We show how to manage the number of active bicliques to improve running time and to stay within memory limits. Our computational results reveal that the fractional binary rank is not multiplicative with respect to the Kronecker product. Hence, there are binary matrices, and bipartite graphs, respectively, such as the Domino, where the asymptotic fractional binary rank is strictly smaller than the fractional binary rank. While we used our algorithm to reduce the upper bound, we formally prove that the fractional biclique cover number is a lower bound, which is at least as good as the widely used isolating (or fooling set) bound. For the Domino, we obtain that the asymptotic fractional binary rank lies in the interval [2,2.373]. Since our computational resources are not sufficient to further reduce the upper bound, we encourage further exploration using more substantial computing resources or further mathematical engineering techniques to narrow the gap and advance our understanding of biclique partitions, particularly, to settle the open question whether binary rank and biclique partition number are multiplicative with respect to the Kronecker product.

Cite as

Angikar Ghosal and Andreas Karrenbauer. Engineering Insights into Biclique Partitions and Fractional Binary Ranks of Matrices. In 23rd International Symposium on Experimental Algorithms (SEA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 338, pp. 18:1-18:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{ghosal_et_al:LIPIcs.SEA.2025.18,
  author =	{Ghosal, Angikar and Karrenbauer, Andreas},
  title =	{{Engineering Insights into Biclique Partitions and Fractional Binary Ranks of Matrices}},
  booktitle =	{23rd International Symposium on Experimental Algorithms (SEA 2025)},
  pages =	{18:1--18:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-375-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{338},
  editor =	{Mutzel, Petra and Prezza, Nicola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2025.18},
  URN =		{urn:nbn:de:0030-drops-232568},
  doi =		{10.4230/LIPIcs.SEA.2025.18},
  annote =	{Keywords: Asymptotic Binary Rank, Algorithm Engineering, Combinatorics of Bipartite Graphs, Linear Programming}
}

Document

DOI: 10.4230/LIPIcs.IPEC.2024.8

Kernelization for Orthogonality Dimension

Authors: Ishay Haviv and Dror Rabinovich

Published in: LIPIcs, Volume 321, 19th International Symposium on Parameterized and Exact Computation (IPEC 2024)

Abstract

The orthogonality dimension of a graph over ℝ is the smallest integer d for which one can assign to every vertex a nonzero vector in ℝ^d such that every two adjacent vertices receive orthogonal vectors. For an integer d, the d-Ortho-Dim_ℝ problem asks to decide whether the orthogonality dimension of a given graph over ℝ is at most d. We prove that for every integer d ≥ 3, the d-Ortho-Dim_ℝ problem parameterized by the vertex cover number k admits a kernel with O(k^{d-1}) vertices and bit-size O(k^{d-1} ⋅ log k). We complement this result by a nearly matching lower bound, showing that for any ε > 0, the problem admits no kernel of bit-size O(k^{d-1-ε}) unless NP ⊆ coNP/poly. We further study the kernelizability of orthogonality dimension problems in additional settings, including over general fields and under various structural parameterizations.

Cite as

Ishay Haviv and Dror Rabinovich. Kernelization for Orthogonality Dimension. In 19th International Symposium on Parameterized and Exact Computation (IPEC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 321, pp. 8:1-8:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{haviv_et_al:LIPIcs.IPEC.2024.8,
  author =	{Haviv, Ishay and Rabinovich, Dror},
  title =	{{Kernelization for Orthogonality Dimension}},
  booktitle =	{19th International Symposium on Parameterized and Exact Computation (IPEC 2024)},
  pages =	{8:1--8:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-353-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{321},
  editor =	{Bonnet, \'{E}douard and Rz\k{a}\.{z}ewski, Pawe{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2024.8},
  URN =		{urn:nbn:de:0030-drops-222341},
  doi =		{10.4230/LIPIcs.IPEC.2024.8},
  annote =	{Keywords: Orthogonality dimension, Fixed-parameter tractability, Kernelization, Graph coloring}
}

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}
}

20 Search Results for "Haviv, Ishay"

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Thanks for your feedback!

Could not send message