Source author record

Igor Shinkar

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computational Complexity Data Structures and Algorithms math.CO Discrete Mathematics math.MG math.PR Social and Information Networks

Catalog footprint

Research overview

12works

7topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

On Mappings on the Hypercube with Small Average Stretch

Let $A \subseteq \{0,1\}^n$ be a set of size $2^{n-1}$ , and let $ϕ\colon \{0,1\}^{n-1} \to A$ be a bijection. We define the average stretch of $ϕ$ as ${\sf avgStretch}(ϕ) = {\mathbb E}[{\sf dist}(ϕ(x),ϕ(x'))]$ , where the expectation is taken over uniformly random $x,x' \in \{0,1\}^{n-1}$ that differ in exactly one coordinate. In this paper we continue the line of research studying mappings on the discrete hypercube with small average stretch. We prove the following results. (1) For any set $A \subseteq \{0,1\}^n$ of density $1/2$ there exists a bijection $ϕ_A \colon \{0,1\}^{n-1} \to A$ such that ${\sf avgstretch}(ϕ_A) = O(\sqrt{n})$ . (2) For $n = 3^k$ let $A_{{\sf rec\text{-}maj}} = \{x \in \{0,1\}^n : {\sf rec\text{-}maj}(x) = 1\}$ , where ${\sf rec\text{-}maj} : \{0,1\}^n \to \{0,1\}$ is the function recursive majority of 3's. There exists a bijection $ϕ_{{\sf rec\text{-}maj}} \colon \{0,1\}^{n-1} \to A_{\sf rec\text{-}maj}$ such that ${\sf avgstretch}(ϕ_{\sf rec\text{-}maj}) = O(1)$ . (3) Let $A_{\sf tribes} = \{x \in \{0,1\}^n : {\sf tribes}(x) = 1\}$ . There exists a bijection $ϕ_{\sf tribes} \colon \{0,1\}^{n-1} \to A_{\sf tribes}$ such that ${\sf avgstretch}(ϕ_{\sf tribes}) = O(\log(n))$ . These results answer the questions raised by Benjamini et al.\ (FOCS 2014).

preprint2022arXiv

Sorting Networks On Restricted Topologies

The sorting number of a graph with $n$ vertices is the minimum depth of a sorting network with $n$ inputs and outputs that uses only the edges of the graph to perform comparisons. Many known results on sorting networks can be stated in terms of sorting numbers of different classes of graphs. In this paper we show the following general results about the sorting number of graphs. Any $n$ -vertex graph that contains a simple path of length $d$ has a sorting network of depth $O(n \log(n/d))$ . Any $n$ -vertex graph with maximal degree $Δ$ has a sorting network of depth $O(Δn)$ . We also provide several results that relate the sorting number of a graph with its routing number, size of its maximal matching, and other well known graph properties. Additionally, we give some new bounds on the sorting number for some typical graphs.

preprint2022arXiv

Worst-Case to Average-Case Reductions via Additive Combinatorics

We present a new framework for designing worst-case to average-case reductions. For a large class of problems, it provides an explicit transformation of algorithms running in time $T$ that are only correct on a small (subconstant) fraction of their inputs into algorithms running in time $\widetilde{O}(T)$ that are correct on all inputs. Using our framework, we obtain such efficient worst-case to average-case reductions for fundamental problems in a variety of computational models; namely, algorithms for matrix multiplication, streaming algorithms for the online matrix-vector multiplication problem, and static data structures for all linear problems as well as for the multivariate polynomial evaluation problem. Our techniques crucially rely on additive combinatorics. In particular, we show a local correction lemma that relies on a new probabilistic version of the quasi-polynomial Bogolyubov-Ruzsa lemma.

preprint2020arXiv

Relaxed Locally Correctable Codes with Improved Parameters

Locally decodable codes (LDCs) are error-correcting codes $C : Σ^k \to Σ^n$ that admit a local decoding algorithm that recovers each individual bit of the message by querying only a few bits from a noisy codeword. An important question in this line of research is to understand the optimal trade-off between the query complexity of LDCs and their block length. Despite importance of these objects, the best known constructions of constant query LDCs have super-polynomial length, and there is a significant gap between the best constructions and the known lower bounds in terms of the block length. For many applications it suffices to consider the weaker notion of relaxed LDCs (RLDCs), which allows the local decoding algorithm to abort if by querying a few bits it detects that the input is not a codeword. This relaxation turned out to allow decoding algorithms with constant query complexity for codes with almost linear length. Specifically, [BGH+06] constructed an $O(q)$ -query RLDC that encodes a message of length $k$ using a codeword of block length $n = O(k^{1+1/\sqrt{q}})$ . In this work we improve the parameters of [BGH+06] by constructing an $O(q)$ -query RLDC that encodes a message of length $k$ using a codeword of block length $O(k^{1+1/{q}})$ . This construction matches (up to a multiplicative constant factor) the lower bounds of [KT00, Woo07] for constant query LDCs, thus making progress toward understanding the gap between LDCs and RLDCs in the constant query regime. In fact, our construction extends to the stronger notion of relaxed locally correctable codes (RLCCs), introduced in [GRR18], where given a noisy codeword the correcting algorithm either recovers each individual bit of the codeword by only reading a small part of the input, or aborts if the input is detected to be corrupt.

preprint2020arXiv

Toward Probabilistic Checking against Non-Signaling Strategies with Constant Locality

Non-signaling strategies are a generalization of quantum strategies that have been studied in physics over the past three decades. Recently, they have found applications in theoretical computer science, including to proving inapproximability results for linear programming and to constructing protocols for delegating computation. A central tool for these applications is probabilistically checkable proof (PCPs) systems that are sound against non-signaling strategies. In this paper we show, assuming a certain geometrical hypothesis about noise robustness of non-signaling proofs (or, equivalently, about robustness to noise of solutions to the Sherali-Adams linear program), that a slight variant of the parallel repetition of the exponential-length constant-query PCP construction due to Arora et al. (JACM 1998) is sound against non-signaling strategies with constant locality. Our proof relies on the analysis of the linearity test and agreement test (also known as the direct product test) in the non-signaling setting.

preprint2016arXiv

An $\widetilde{O}(n)$ Queries Adaptive Tester for Unateness

We present an adaptive tester for the unateness property of Boolean functions. Given a function $f:\{0,1\}^n \to \{0,1\}$ the tester makes $O(n \log(n)/ε)$ adaptive queries to the function. The tester always accepts a unate function, and rejects with probability at least 0.9 if a function is $ε$ -far from being unate.

preprint2015arXiv

A Counterexample to Monotonicity of Relative Mass in Random Walks

For a finite undirected graph $G = (V,E)$ , let $p_{u,v}(t)$ denote the probability that a continuous-time random walk starting at vertex $u$ is in $v$ at time $t$ . In this note we give an example of a Cayley graph $G$ and two vertices $u,v \in G$ for which the function $r_{u,v}(t) = \frac{p_{u,v}(t)}{p_{u,u}(t)} \qquad t \geq 0$ is not monotonically non-decreasing. This answers a question asked by Peres in 2013.

preprint2015arXiv

On Lipschitz Bijections between Boolean Functions

For two functions $f,g:\{0,1\}^n\to\{0,1\}$ a mapping $ψ:\{0,1\}^n\to\{0,1\}^n$ is said to be a $\textit{mapping from $f $to$ g$}$ if it is a bijection and $f(z)=g(ψ(z))$ for every $z\in\{0,1\}^n$ . In this paper we study Lipschitz mappings between boolean functions. Our first result gives a construction of a $C$ -Lipschitz mapping from the ${\sf Majority}$ function to the ${\sf Dictator}$ function for some universal constant $C$ . On the other hand, there is no $n/2$ -Lipschitz mapping in the other direction, namely from the ${\sf Dictator}$ function to the ${\sf Majority}$ function. This answers an open problem posed by Daniel Varga in the paper of Benjamini et al. (FOCS 2014). We also show a mapping from ${\sf Dictator}$ to ${\sf XOR}$ that is 3-local, 2-Lipschitz, and its inverse is $O(\log(n))$ -Lipschitz, where by $L$ -local mapping we mean that each of its output bits depends on at most $L$ input bits. Next, we consider the problem of finding functions such that any mapping between them must have large \emph{average stretch}, where the average stretch of a mapping $ϕ$ is defined as ${\sf avgStretch}(ϕ) = {\mathbb E}_{x,i}[dist(ϕ(x),ϕ(x+e_i)]$ . We show that any mapping $ϕ$ from ${\sf XOR}$ to ${\sf Majority}$ must satisfy ${\sf avgStretch}(ϕ) \geq Ω(\sqrt{n})$ . In some sense, this gives a "function analogue" to the question of Benjamini et al. (FOCS 2014), who asked whether there exists a set $A \subset \{0,1\}^n$ of density 0.5 such that any bijection from $\{0,1\}^{n-1}$ to $A$ has large average stretch. Finally, we show that for a random balanced function $f:\{0,1\}^n\to\{0,1\}^n$ with high probability there is a mapping $ϕ$ from ${\sf Dictator}$ to $f$ such that both $ϕ$ and $ϕ^{-1}$ have constant average stretch. In particular, this implies that one cannot obtain lower bounds on average stretch by taking uniformly random functions.

preprint2015arXiv

On Percolation and $NP$ -Hardness

We consider the robustness of computational hardness of problems whose input is obtained by applying independent random deletions to worst-case instances. For some classical $NP$ -hard problems on graphs, such as Coloring, Vertex-Cover, and Hamiltonicity, we examine the complexity of these problems when edges (or vertices) of an arbitrary graph are deleted independently with probability $1-p > 0$ . We prove that for $n$ -vertex graphs, these problems remain as hard as in the worst-case, as long as $p > \frac{1}{n^{1-ε}}$ for arbitrary $ε\in (0,1)$ , unless $NP \subseteq BPP$ . We also prove hardness results for Constraint Satisfaction Problems, where random deletions are applied to clauses or variables, as well as the Subset-Sum problem, where items of a given instance are deleted at random.

preprint2014arXiv

Acquaintance Time of a Graph

We define the following parameter of connected graphs. For a given graph $G$ we place one agent in each vertex of $G$ . Every pair of agents sharing a common edge is declared to be acquainted. In each round we choose some matching of $G$ (not necessarily a maximal matching), and for each edge in the matching the agents on this edge swap places. After the swap, again, every pair of agents sharing a common edge become acquainted, and the process continues. We define the \emph{acquaintance time} of a graph $G$ , denoted by $AC(G)$ , to be the minimal number of rounds required until every two agents are acquainted. We first study the acquaintance time for some natural families of graphs including the path, expanders, the binary tree, and the complete bipartite graph. We also show that for all positive integers $n$ and $k \leq n^{1.5}$ there exists an $n$ -vertex graph $G$ such that $AC(G) =Θ(k)$ . We also prove that for all $n$ -vertex connected graphs $G$ we have $AC(G) = O\left(\frac{n^2}{\log(n)/\log\log(n)}\right)$ , improving the $O(n^2)$ trivial upper bound achieved by sequentially letting each agent perform depth-first search along a spanning tree of $G$ . Studying the computational complexity of this problem, we prove that for any constant $t \geq 1$ the problem of deciding that a given graph $G$ has $AC(G) \leq t$ or $AC(G) \geq 2t$ is $\mathcal{NP}$ -complete. That is, $AC(G)$ is $\mathcal{NP}$ -hard to approximate within multiplicative factor of 2, as well as within any additive constant factor. On the algorithmic side, we give a deterministic algorithm that given a graph $G$ with $AC(G)=1$ finds a ${\lceil n/c\rceil}$ -rounds strategy for acquaintance in time $n^{c+O(1)}$ . We also design a randomized polynomial time algorithm that given a graph $G$ with $AC(G)=1$ finds with high probability an $O(\log(n))$ -rounds strategy for acquaintance.

preprint2013arXiv

A Tight Upper Bound on Acquaintance Time of Graphs

In this note we confirm a conjecture raised by Benjamini et al. \cite{BST} on the acquaintance time of graphs, proving that for all graphs $G$ with $n$ vertices it holds that $\AC(G) = O(n^{3/2})$, which is tight up to a multiplicative constant. This is done by proving that for all graphs $G$ with $n$ vertices and maximal degree $Δ$ it holds that $\AC(G) \leq 20 Δn$. Combining this with the bound $\AC(G) \leq O(n^2/Δ)$ from \cite{BST} gives the foregoing uniform upper bound of all $n$ -vertex graphs. We also prove that for the $n$ -vertex path $P_n$ it holds that $\AC(P_n)=n-2$. In addition we show that the barbell graph $B_n$ consisting of two cliques of sizes $\ceil{n/2}$ and $\floor{n/2}$ connected by a single edge also has $\AC(B_n) = n-2$. This shows that it is possible to add $Ω(n^2)$ edges to $P_n$ without changing the $\AC$ value of the graph.

preprint2013arXiv

Bi-Lipschitz Bijection between the Boolean Cube and the Hamming Ball

We construct a bi-Lipschitz bijection from the Boolean cube to the Hamming ball of equal volume. More precisely, we show that for all even n there exists an explicit bijection f from the n-dimensional Boolean cube to the Hamming ball of equal volume embedded in (n+1)-dimensional Boolean cube, such that for all x and y it holds that distance(x,y) / 5 <= distance(f(x),f(y)) <= 4 distance(x,y) where distance(,) denotes the Hamming distance. In particular, this implies that the Hamming ball is bi-Lipschitz transitive. This result gives a strong negative answer to an open problem of Lovett and Viola [CC 2012], who raised the question in the context of sampling distributions in low-level complexity classes. The conceptual implication is that the problem of proving lower bounds in the context of sampling distributions will require some new ideas beyond the sensitivity-based structural results of Boppana [IPL 97]. We study the mapping f further and show that it (and its inverse) are computable in DLOGTIME-uniform TC0, but not in AC0. Moreover, we prove that f is "approximately local" in the sense that all but the last output bit of f are essentially determined by a single input bit.

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.

Igor Shinkar

Research overview

Is this your work?

12 publications

On Mappings on the Hypercube with Small Average Stretch

Sorting Networks On Restricted Topologies

Worst-Case to Average-Case Reductions via Additive Combinatorics

Relaxed Locally Correctable Codes with Improved Parameters

Toward Probabilistic Checking against Non-Signaling Strategies with Constant Locality

An $\widetilde{O}(n)$ Queries Adaptive Tester for Unateness

A Counterexample to Monotonicity of Relative Mass in Random Walks

On Lipschitz Bijections between Boolean Functions

On Percolation and $NP$ -Hardness

Acquaintance Time of a Graph

A Tight Upper Bound on Acquaintance Time of Graphs

Bi-Lipschitz Bijection between the Boolean Cube and the Hamming Ball

See the researcher in context

Building this map preview

Igor Shinkar

Research overview

Is this your work?

12 publications

On Mappings on the Hypercube with Small Average Stretch

Sorting Networks On Restricted Topologies

Worst-Case to Average-Case Reductions via Additive Combinatorics

Relaxed Locally Correctable Codes with Improved Parameters

Toward Probabilistic Checking against Non-Signaling Strategies with Constant Locality

An O~(n)\widetilde{O}(n)O(n) Queries Adaptive Tester for Unateness

A Counterexample to Monotonicity of Relative Mass in Random Walks

On Lipschitz Bijections between Boolean Functions

On Percolation and NPNPNP-Hardness

Acquaintance Time of a Graph

A Tight Upper Bound on Acquaintance Time of Graphs

Bi-Lipschitz Bijection between the Boolean Cube and the Hamming Ball

See the researcher in context

Building this map preview

An $\widetilde{O}(n)$ Queries Adaptive Tester for Unateness

On Percolation and $NP$ -Hardness