All reports by Author Igor Shinkar:

__
TR22-177
| 7th December 2022
__

Vahid Reza Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar, Sathyawageeswar Subramanian#### Quantum Worst-Case to Average-Case Reductions for All Linear Problems

__
TR22-020
| 18th February 2022
__

Vahid Reza Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar#### Worst-Case to Average-Case Reductions via Additive Combinatorics

__
TR20-144
| 7th September 2020
__

Mohammad Jahanara, Sajin Koroth, Igor Shinkar#### Toward Probabilistic Checking against Non-Signaling Strategies with Constant Locality

__
TR20-142
| 15th September 2020
__

Vahid Reza Asadi, Igor Shinkar#### Relaxed Locally Correctable Codes with Improved Parameters

__
TR20-113
| 27th July 2020
__

Alessandro Chiesa, Tom Gur, Igor Shinkar#### Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity

__
TR19-070
| 14th May 2019
__

Alessandro Chiesa, Peter Manohar, Igor Shinkar#### On Local Testability in the Non-Signaling Setting

Revisions: 1

__
TR16-126
| 8th August 2016
__

Subhash Khot, Igor Shinkar#### An $\widetilde{O}(n)$ Queries Adaptive Tester for Unateness

__
TR15-132
| 13th August 2015
__

Daniel Reichman, Igor Shinkar#### On Percolation and NP-Hardness

Revisions: 2

__
TR15-013
| 28th January 2015
__

Subhash Khot, Igor Shinkar#### On Hardness of Approximating the Parameterized Clique Problem

__
TR14-160
| 27th November 2014
__

Gil Cohen, Igor Shinkar#### Zero-Fixing Extractors for Sub-Logarithmic Entropy

__
TR14-099
| 7th August 2014
__

Gil Cohen, Igor Shinkar#### The Complexity of DNF of Parities

__
TR14-002
| 8th January 2014
__

Roee David, Irit Dinur, Elazar Goldenberg, Guy Kindler, Igor Shinkar#### Direct Sum Testing

Revisions: 1

__
TR13-148
| 26th October 2013
__

Irit Dinur, Igor Shinkar#### On the Conditional Hardness of Coloring a 4-colorable Graph with Super-Constant Number of Colors

__
TR13-138
| 5th October 2013
__

Itai Benjamini, Gil Cohen, Igor Shinkar#### Bi-Lipschitz Bijection between the Boolean Cube and the Hamming Ball

Revisions: 1

__
TR12-095
| 23rd July 2012
__

Avraham Ben-Aroya, Igor Shinkar#### A Note on Subspace Evasive Sets

__
TR12-021
| 14th March 2012
__

Oded Goldreich, Igor Shinkar#### Two-Sided Error Proximity Oblivious Testing

Revisions: 4

Vahid Reza Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar, Sathyawageeswar Subramanian

We study the problem of designing worst-case to average-case reductions for quantum algorithms. For all linear problems, we provide an explicit and efficient transformation of quantum algorithms that are only correct on a small (even sub-constant) fraction of their inputs into ones that are correct on all inputs. This stands ... more >>>

Vahid Reza Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar

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 ... more >>>

Mohammad Jahanara, Sajin Koroth, Igor Shinkar

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 ... more >>>

Vahid Reza Asadi, Igor Shinkar

Locally decodable codes (LDCs) are error-correcting codes $C : \Sigma^k \to \Sigma^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 ... more >>>

Alessandro Chiesa, Tom Gur, Igor Shinkar

Locally correctable codes (LCCs) are error correcting codes C : \Sigma^k \to \Sigma^n which admit local algorithms that correct any individual symbol of a corrupted codeword via a minuscule number of queries. This notion is stronger than that of locally decodable codes (LDCs), where the goal is to only recover ... more >>>

Alessandro Chiesa, Peter Manohar, Igor Shinkar

Non-signaling strategies are a generalization of quantum strategies that have been studied in physics for decades, and have recently found applications in theoretical computer science. These applications motivate the study of local-to-global phenomena for non-signaling functions.

We present general results about the local testability of linear codes in the non-signaling ... more >>>

Subhash Khot, Igor Shinkar

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)/\epsilon)$ adaptive queries to the function. The tester always accepts a unate function, and rejects with probability at least 0.9 any function that is $\epsilon$-far from being unate.

more >>>

Daniel Reichman, Igor Shinkar

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 ...
more >>>

Subhash Khot, Igor Shinkar

In the $Gap-clique(k, \frac{k}{2})$ problem, the input is an $n$-vertex graph $G$, and the goal is to decide whether $G$ contains a clique of size $k$ or contains no clique of size $\frac{k}{2}$. It is an open question in the study of fixed parameterized tractability whether the $Gap-clique(k, \frac{k}{2})$ problem ... more >>>

Gil Cohen, Igor Shinkar

An $(n,k)$-bit-fixing source is a distribution on $n$ bit strings, that is fixed on $n-k$ of the coordinates, and jointly uniform on the remaining $k$ bits. Explicit constructions of bit-fixing extractors by Gabizon, Raz and Shaltiel [SICOMP 2006] and Rao [CCC 2009], extract $(1-o(1)) \cdot k$ bits for $k = ... more >>>

Gil Cohen, Igor Shinkar

We study depth 3 circuits of the form $\mathrm{OR} \circ \mathrm{AND} \circ \mathrm{XOR}$, or equivalently -- DNF of parities. This model was first explicitly studied by Jukna (CPC'06) who obtained a $2^{\Omega(n)}$ lower bound for explicit functions. Several related models have gained attention in the last few years, such as ... more >>>

Roee David, Irit Dinur, Elazar Goldenberg, Guy Kindler, Igor Shinkar

For a string $a \in \{0,1\}^n$ its $k$-fold direct sum encoding is a function $f_a$ that takes as input sets $S \subseteq [n]$ of

size $k$ and outputs $f_a(S) = \sum_{i \in S} a_i$.

In this paper we are interested in the Direct Sum Testing Problem,

where we are given ...
more >>>

Irit Dinur, Igor Shinkar

For $3 \leq q < Q$ we consider the $\text{ApproxColoring}(q,Q)$ problem of deciding for a given graph $G$ whether $\chi(G) \leq q$ or $\chi(G) \geq Q$. It was show in [DMR06] that the problem $\text{ApproxColoring}(q,Q)$ is NP-hard for $q=3,4$ and arbitrary large constant $Q$ under variants of the Unique Games ... more >>>

Itai Benjamini, Gil Cohen, Igor Shinkar

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 \in {\mathbb N}$ there exists an explicit bijection $\psi \colon \{0,1\}^n \to \left\{ x \in \{0,1\}^{n+1} \colon |x| > n/2 \right\}$ such that for every ... more >>>

Avraham Ben-Aroya, Igor Shinkar

A subspace-evasive set over a field ${\mathbb F}$ is a subset of ${\mathbb F}^n$ that has small intersection with any low-dimensional affine subspace of ${\mathbb F}^n$. Interest in subspace evasive sets began in the work of Pudlák and Rödl (Quaderni di Matematica 2004). More recently, Guruswami (CCC 2011) showed that ... more >>>

Oded Goldreich, Igor Shinkar

Loosely speaking, a proximity-oblivious (property) tester is a randomized algorithm that makes a constant number of queries to a tested object and distinguishes objects that have a predetermined property from those that lack it. Specifically, for some threshold probability $c$, objects having the property are accepted with probability at least ... more >>>