Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Igor Shinkar:

TR16-126 | 8th August 2016
Subhash Khot, Igor Shinkar

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)/\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 >>>

TR15-132 | 13th August 2015
Daniel Reichman, Igor Shinkar

On Percolation and NP-Hardness

Revisions: 2

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

TR15-013 | 28th January 2015
Subhash Khot, Igor Shinkar

On Hardness of Approximating the Parameterized Clique Problem

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

TR14-160 | 27th November 2014
Gil Cohen, Igor Shinkar

Zero-Fixing Extractors for Sub-Logarithmic Entropy

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

TR14-099 | 7th August 2014
Gil Cohen, Igor Shinkar

The Complexity of DNF of Parities

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

TR14-002 | 8th January 2014
Roee David, Irit Dinur, Elazar Goldenberg, Guy Kindler, Igor Shinkar

Direct Sum Testing

Revisions: 1

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

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

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

TR13-138 | 5th October 2013
Itai Benjamini, Gil Cohen, Igor Shinkar

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

Revisions: 1

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

TR12-095 | 23rd July 2012
Avraham Ben-Aroya, Igor Shinkar

A Note on Subspace Evasive Sets

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

TR12-021 | 14th March 2012
Oded Goldreich, Igor Shinkar

Two-Sided Error Proximity Oblivious Testing

Revisions: 4

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

ISSN 1433-8092 | Imprint