Igor Shinkar

STOC Conference 2024 Conference Paper

On the Power of Interactive Proofs for Learning

• Tom Gur
• Mohammad Mahdi Jahanara
• Mohammad Mahdi Khodabandeh
• Ninad Rajgopal
• Bahar Salamatian
• Igor Shinkar

We continue the study of doubly-efficient proof systems for verifying agnostic PAC learning, for which we obtain the following results. We construct an interactive protocol for learning the t largest Fourier characters of a given function f ∶ {0,1} n → {0,1} up to an arbitrarily small error, wherein the verifier uses poly ( t ) random examples. This improves upon the Interactive Goldreich-Levin protocol of Goldwasser, Rothblum, Shafer, and Yehudayoff (ITCS 2021) whose sample complexity is poly ( t , n ). For agnostically learning the class AC 0 [2] under the uniform distribution, we build on the work of Carmosino, Impagliazzo, Kabanets, and Kolokolova (APPROX/RANDOM 2017) and design an interactive protocol, where given a function f ∶ {0,1} n → {0,1}, the verifier learns the closest hypothesis up to polylog ( n ) multiplicative factor, using quasi-polynomially many random examples. In contrast, this class has been notoriously resistant even for constructing realisable learners (without a prover) using random examples. For agnostically learning k -juntas under the uniform distribution, we obtain an interactive protocol, where the verifier uses O (2 k ) random examples to a given function f ∶ {0,1} n → {0,1}. Crucially, the sample complexity of the verifier is independent of n . We also show that if we do not insist on doubly-efficient proof systems, then the model becomes trivial. Specifically, we show a protocol for an arbitrary class C of Boolean functions in the distribution-free setting, where the verifier uses O (1) labeled examples to learn f .

SODA Conference 2024 Conference Paper

Quantum Worst-Case to Average-Case Reductions for All Linear Problems

• Vahid R. Asadi
• Alexander Golovnev
• Tom Gur
• Igor Shinkar
• Sathyawageeswar Subramanian

STOC Conference 2022 Conference Paper

Worst-case to average-case reductions via additive combinatorics

• Vahid R. 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 O ( T ) that are correct on all inputs.

SODA Conference 2020 Conference Paper

Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity

• Alessandro Chiesa
• Tom Gur
• Igor Shinkar

Locally correctable codes (LCCs) are codes C: Σ k → Σ n which admit local algorithms that can correct any individual symbol of a corrupted codeword via a minuscule number of queries. One of the central problems in algorithmic coding theory is to construct O (1)-query LCC with minimal block length. Alas, state-of-the-art of such codes requires exponential block length to admit O (1)-query algorithms for local correction, despite much attention during the last two decades. This lack of progress prompted the study of relaxed LCCs, which allow the correction algorithm to abort (but not err) on small fraction of the locations. This relaxation turned out to allow constant-query correction algorithms for codes with polynomial block length. Specifically, prior work showed that there exist O (1)-query relaxed LCCs that achieve nearly-quartic block length n = k 4+ α, for an arbitrarily small constant α > 0. We construct an O (1)-query relaxed LCC with nearly-linear block length n = k 1+ α, for an arbitrarily small constant α > 0. This significantly narrows the gap between the lower bound which states that there are no O (1)-query relaxed LCCs with block length n = k 1+ o (1). In particular, this resolves an open problem raised by Gur, Ramnarayan, and Rothblum (ITCS 2018).

NeurIPS Conference 2017 Conference Paper

A graph-theoretic approach to multitasking

• Noga Alon
• Daniel Reichman
• Igor Shinkar
• Tal Wagner
• Sebastian Musslick
• Jonathan Cohen
• Tom Griffiths
• Biswadip Dey

A key feature of neural network architectures is their ability to support the simultaneous interaction among large numbers of units in the learning and processing of representations. However, how the richness of such interactions trades off against the ability of a network to simultaneously carry out multiple independent processes -- a salient limitation in many domains of human cognition -- remains largely unexplored. In this paper we use a graph-theoretic analysis of network architecture to address this question, where tasks are represented as edges in a bipartite graph $G=(A \cup B, E)$. We define a new measure of multitasking capacity of such networks, based on the assumptions that tasks that \emph{need} to be multitasked rely on independent resources, i. e. , form a matching, and that tasks \emph{can} be performed without interference if they form an induced matching. Our main result is an inherent tradeoff between the multitasking capacity and the average degree of the network that holds \emph{regardless of the network architecture}. These results are also extended to networks of depth greater than $2$. On the positive side, we demonstrate that networks that are random-like (e. g. , locally sparse) can have desirable multitasking properties. Our results shed light into the parallel-processing limitations of neural systems and provide insights that may be useful for the analysis and design of parallel architectures.

FOCS Conference 2014 Conference Paper

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

• 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 E N there exists an explicit bijection ψ: {0, 1} n → {x E {0, 1}n+1: |x| > n/2} such that for every x ≠ y E {0, 1} n+1 it holds that 1/5 ≤ dist(ψ(x), ψ(y)) ≤ 4 5 - dist(x, y) where dist(·, ·) 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 requires ideas beyond the sensitivity-based structural results of Boppana [IPL 97]. We study the mapping ψ further and show that it (and its inverse) are computable in DLOGTIME-uniform TC°, but not in AC°. Moreover, we prove that ψ is “approximately local” in the sense that all but the last output bit of ψ are essentially determined by a single input bit.