BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Ishay Haviv

Ishay Haviv appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Information Theorymath.COmath.ITData Structures and AlgorithmsComputational ComplexityDiscrete Mathematicsmath.PR

Catalog footprint

What is connected

11works
7topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

11 published item(s)

preprint2022arXiv

On the Subspace Choosability in Graphs

A graph $G$ is said to be $k$-subspace choosable over a field $\mathbb{F}$ if for every assignment of $k$-dimensional subspaces of some finite-dimensional vector space over $\mathbb{F}$ to the vertices of $G$, it is possible to choose for each vertex a nonzero vector from its subspace so that adjacent vertices receive orthogonal vectors over $\mathbb{F} $. The subspace choice number of $G$ over $\mathbb{F}$ is the smallest integer $k$ for which $G$ is $k$-subspace choosable over $\mathbb{F}$. This graph parameter, introduced by Haynes, Park, Schaeffer, Webster, and Mitchell (Electron. J. Comb., 2010), is inspired by well-studied variants of the chromatic number of graphs, such as the (color) choice number and the orthogonality dimension. We study the subspace choice number of graphs over various fields. We first prove that the subspace choice number of every graph with average degree $d$ is at least $Ω(\sqrt{d/\ln d})$ over any field. We then focus on bipartite graphs and consider the problem of estimating, for a given integer $k$, the smallest integer $m$ for which the subspace choice number of the complete bipartite graph $K_{k,m}$ over a field $\mathbb{F}$ exceeds $k$. We prove upper and lower bounds on this quantity as well as for several extensions of this problem. Our results imply a substantial difference between the behavior of the choice number and that of the subspace choice number. We also consider the computational aspect of the subspace choice number, and show that for every $k \geq 3$ it is $\mathsf{NP}$-hard to decide whether the subspace choice number of a given bipartite graph over $\mathbb{F}$ is at most $k$, provided that $\mathbb{F}$ is either the real field or any finite field.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Upper Bounds on the Boolean Rank of Kronecker Products

The Boolean rank of a $0,1$-matrix $A$, denoted $R_\mathbb{B}(A)$, is the smallest number of monochromatic combinatorial rectangles needed to cover the $1$-entries of $A$. In 1988, de Caen, Gregory, and Pullman asked if the Boolean rank of the Kronecker product $C_n \otimes C_n$ is strictly smaller than the square of $R_\mathbb{B}(C_n)$, where $C_n$ is the $n \times n$ matrix with zeros on the diagonal and ones everywhere else (Carib. Conf. Comb. & Comp., 1988). A positive answer was given by Watts for $n=4$ (Linear Alg. and its Appl., 2001). A result of Karchmer, Kushilevitz, and Nisan, motivated by direct-sum questions in non-deterministic communication complexity, implies that the Boolean rank of $C_n \otimes C_n$ grows linearly in that of $C_n$ (SIAM J. Disc. Math., 1995), and thus $R_\mathbb{B}(C_n \otimes C_n) < R_\mathbb{B}(C_n)^2$ for every sufficiently large $n$. Their proof relies on a probabilistic argument. In this work, we present a general method for proving upper bounds on the Boolean rank of Kronecker products of $0,1$-matrices. We use it to affirmatively settle the question of de Caen et al. for all integers $n \geq 7$. We further provide an explicit construction of a cover of $C_n \otimes C_n$, whose number of rectangles nearly matches the optimal asymptotic bound. Our method for proving upper bounds on the Boolean rank of Kronecker products might find applications in different settings as well. We express its potential applicability by extending it to the wider framework of spanoids, recently introduced by Dvir, Gopi, Gu, and Wigderson (SIAM J. Comput., 2020).

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Minimizing the alphabet size of erasure codes with restricted decoding sets

A Maximum Distance Separable code over an alphabet $F$ is defined via an encoding function $C:F^k \rightarrow F^n$ that allows to retrieve a message $m \in F^k$ from the codeword $C(m)$ even after erasing any $n-k$ of its symbols. The minimum possible alphabet size of general (non-linear) MDS codes for given parameters $n$ and $k$ is unknown and forms one of the central open problems in coding theory. The paper initiates the study of the alphabet size of codes in a generalized setting where the coding scheme is required to handle a pre-specified subset of all possible erasure patterns, naturally represented by an $n$-vertex $k$-uniform hypergraph. We relate the minimum possible alphabet size of such codes to the strong chromatic number of the hypergraph and analyze the tightness of the obtained bounds for both the linear and non-linear settings. We further consider variations of the problem which allow a small probability of decoding error.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Task-based Solutions to Embedded Index Coding

In the index coding problem a sender holds a message $x \in \{0,1\}^n$ and wishes to broadcast information to $n$ receivers in a way that enables the $i$th receiver to retrieve the $i$th bit $x_i$. Every receiver has prior side information comprising a subset of the bits of $x$, and the goal is to minimize the length of the information sent via the broadcast channel. Porter and Wootters have recently introduced the model of embedded index coding, where the receivers also play the role of the sender and the goal is to minimize the total length of their broadcast information. An embedded index code is said to be task-based if every receiver retrieves its bit based only on the information provided by one of the receivers. This paper studies the effect of the task-based restriction on linear embedded index coding. It is shown that for certain side information maps there exists a linear embedded index code of length quadratically smaller than that of any task-based embedded index code. The result attains, up to a multiplicative constant, the largest possible gap between the two quantities. The proof is by an explicit construction and the analysis involves spectral techniques.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

The List-Decoding Size of Fourier-Sparse Boolean Functions

A function defined on the Boolean hypercube is $k$-Fourier-sparse if it has at most $k$ nonzero Fourier coefficients. For a function $f: \mathbb{F}_2^n \rightarrow \mathbb{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 \cdot 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).

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

The Restricted Isometry Property of Subsampled Fourier Matrices

A matrix $A \in \mathbb{C}^{q \times N}$ satisfies the restricted isometry property of order $k$ with constant $\varepsilon$ if it preserves the $\ell_2$ norm of all $k$-sparse vectors up to a factor of $1\pm \varepsilon$. We prove that a matrix $A$ obtained by randomly sampling $q = O(k \cdot \log^2 k \cdot \log N)$ rows from an $N \times N$ Fourier matrix satisfies the restricted isometry property of order $k$ with a fixed $\varepsilon$ with high probability. This improves on Rudelson and Vershynin (Comm. Pure Appl. Math., 2008), its subsequent improvements, and Bourgain (GAFA Seminar Notes, 2014).

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Sunflowers and Testing Triangle-Freeness of Functions

A function $f: \mathbb{F}_2^n \rightarrow \{0,1\}$ is triangle-free if there are no $x_1,x_2,x_3 \in \mathbb{F}_2^n$ satisfying $x_1+x_2+x_3=0$ and $f(x_1)=f(x_2)=f(x_3)=1$. In testing triangle-freeness, the goal is to distinguish with high probability triangle-free functions from those that are $\varepsilon$-far from being triangle-free. It was shown by Green that the query complexity of the canonical tester for the problem is upper bounded by a function that depends only on $\varepsilon$ (GAFA, 2005), however the best known upper bound is a tower type function of $1/\varepsilon$. The best known lower bound on the query complexity of the canonical tester is $1/\varepsilon^{13.239}$ (Fu and Kleinberg, RANDOM, 2014). In this work we introduce a new approach to proving lower bounds on the query complexity of triangle-freeness. We relate the problem to combinatorial questions on collections of vectors in $\mathbb{Z}_D^n$ and to sunflower conjectures studied by Alon, Shpilka, and Umans (Comput. Complex., 2013). The relations yield that a refutation of the Weak Sunflower Conjecture over $\mathbb{Z}_4$ implies a super-polynomial lower bound on the query complexity of the canonical tester for triangle-freeness. Our results are extended to testing $k$-cycle-freeness of functions with domain $\mathbb{F}_p^n$ for every $k \geq 3$ and a prime $p$. In addition, we generalize the lower bound of Fu and Kleinberg to $k$-cycle-freeness for $k \geq 4$ by generalizing the construction of uniquely solvable puzzles due to Coppersmith and Winograd (J. Symbolic Comput., 1990).

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

On the Lattice Isomorphism Problem

We study the Lattice Isomorphism Problem (LIP), in which given two lattices L_1 and L_2 the goal is to decide whether there exists an orthogonal linear transformation mapping L_1 to L_2. Our main result is an algorithm for this problem running in time n^{O(n)} times a polynomial in the input size, where n is the rank of the input lattices. A crucial component is a new generalized isolation lemma, which can isolate n linearly independent vectors in a given subset of Z^n and might be useful elsewhere. We also prove that LIP lies in the complexity class SZK.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Beating the Gilbert-Varshamov Bound for Online Channels

In the online channel coding model, a sender wishes to communicate a message to a receiver by transmitting a codeword x =(x_1,...,x_n) in {0,1}^n bit by bit via a channel limited to at most pn corruptions. The channel is online in the sense that at the ith step the channel decides whether to flip the ith bit or not and its decision is based only on the bits transmitted so far, i.e., (x_1,...,x_i). This is in contrast to the classical adversarial channel in which the corruption is chosen by a channel that has full knowledge on the sent codeword x. The best known lower bound on the capacity of both the online channel and the classical adversarial channel is the well-known Gilbert-Varshamov bound. In this paper we prove a lower bound on the capacity of the online channel which beats the Gilbert-Varshamov bound for any positive p such that H(2p) < 0.5 (where H is the binary entropy function). To do so, we prove that for any such p, a code chosen at random combined with the nearest neighbor decoder achieves with high probability a rate strictly higher than the Gilbert-Varshamov bound (for the online channel).

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Linear Index Coding via Semidefinite Programming

In the index coding problem, introduced by Birk and Kol (INFOCOM, 1998), the goal is to broadcast an n bit word to n receivers (one bit per receiver), where the receivers have side information represented by a graph G. The objective is to minimize the length of a codeword sent to all receivers which allows each receiver to learn its bit. For linear index coding, the minimum possible length is known to be equal to a graph parameter called minrank (Bar-Yossef et al., FOCS, 2006). We show a polynomial time algorithm that, given an n vertex graph G with minrank k, finds a linear index code for G of length $\widetilde{O}(n^{f(k)})$, where f(k) depends only on k. For example, for k=3 we obtain f(3) ~ 0.2574. Our algorithm employs a semidefinite program (SDP) introduced by Karger, Motwani and Sudan (J. ACM, 1998) for graph coloring and its refined analysis due to Arora, Chlamtac and Charikar (STOC, 2006). Since the SDP we use is not a relaxation of the minimization problem we consider, a crucial component of our analysis is an upper bound on the objective value of the SDP in terms of the minrank. At the heart of our analysis lies a combinatorial result which may be of independent interest. Namely, we show an exact expression for the maximum possible value of the Lovasz theta-function of a graph with minrank k. This yields a tight gap between two classical upper bounds on the Shannon capacity of a graph.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

On Linear Index Coding for Random Graphs

A sender wishes to broadcast an n character word x in F^n (for a field F) to n receivers R_1,...,R_n. Every receiver has some side information on x consisting of a subset of the characters of x. The side information of the receivers is represented by a graph G on n vertices in which {i,j} is an edge if R_i knows x_j. In the index coding problem the goal is to encode x using a minimum number of characters in F in a way that enables every R_i to retrieve the ith character x_i using the encoded message and the side information. An index code is linear if the encoding is linear, and in this case the minimum possible length is known to be equal to a graph parameter called minrank (Bar-Yossef et al., FOCS'06). Several bounds on the minimum length of an index code for side information graphs G were shown in the study of index coding. However, the minimum length of an index code for the random graph G(n,p) is far from being understood. In this paper we initiate the study of the typical minimum length of a linear index code for G(n,p) over a field F. First, we prove that for every constant size field F and a constant p, the minimum length of a linear index code for G(n,p) over F is almost surely Omega(\sqrt{n}). Second, we introduce and study the following two restricted models of index coding: 1. A locally decodable index code is an index code in which the receivers are allowed to query at most q characters from the encoded message. 2. A low density index code is a linear index code in which every character of the word x affects at most q characters in the encoded message. Equivalently, it is a linear code whose generator matrix has at most q nonzero entries in each row.

0 citations0 reviewsNo code linkedOpen access