12 Search Results for "Efremenko, Klim"


Document
Track A: Algorithms, Complexity and Games
Protecting Single-Hop Radio Networks from Message Drops

Authors: Klim Efremenko, Gillat Kol, Dmitry Paramonov, and Raghuvansh R. Saxena

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)


Abstract
Single-hop radio networks (SHRN) are a well studied abstraction of communication over a wireless channel. In this model, in every round, each of the n participating parties may decide to broadcast a message to all the others, potentially causing collisions. We consider the SHRN model in the presence of stochastic message drops (i.e., erasures), where in every round, the message received by each party is erased (replaced by ⊥) with some small constant probability, independently. Our main result is a constant rate coding scheme, allowing one to run protocols designed to work over the (noiseless) SHRN model over the SHRN model with erasures. Our scheme converts any protocol Π of length at most exponential in n over the SHRN model to a protocol Π' that is resilient to constant fraction of erasures and has length linear in the length of Π. We mention that for the special case where the protocol Π is non-adaptive, i.e., the order of communication is fixed in advance, such a scheme was known. Nevertheless, adaptivity is widely used and is known to hugely boost the power of wireless channels, which makes handling the general case of adaptive protocols Π both important and more challenging. Indeed, to the best of our knowledge, our result is the first constant rate scheme that converts adaptive protocols to noise resilient ones in any multi-party model.

Cite as

Klim Efremenko, Gillat Kol, Dmitry Paramonov, and Raghuvansh R. Saxena. Protecting Single-Hop Radio Networks from Message Drops. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 53:1-53:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{efremenko_et_al:LIPIcs.ICALP.2023.53,
  author =	{Efremenko, Klim and Kol, Gillat and Paramonov, Dmitry and Saxena, Raghuvansh R.},
  title =	{{Protecting Single-Hop Radio Networks from Message Drops}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{53:1--53:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.53},
  URN =		{urn:nbn:de:0030-drops-181059},
  doi =		{10.4230/LIPIcs.ICALP.2023.53},
  annote =	{Keywords: Radio Networks, Interactive Coding, Error Correcting Codes}
}
Document
Noisy Radio Network Lower Bounds via Noiseless Beeping Lower Bounds

Authors: Klim Efremenko, Gillat Kol, Dmitry Paramonov, and Raghuvansh R. Saxena

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)


Abstract
Much of today’s communication is carried out over large wireless systems with different input-output behaviors. In this work, we compare the power of central abstractions of wireless communication through the general notion of boolean symmetric f-channels: In every round of the f-channel, each of its n parties decides to either broadcast or not, and the channel outputs f(m), where m is the number of broadcasting parties. Our first result is that the well studied beeping channel, where f is the threshold-1 function, is not stronger than any other f-channel. To this end, we design a protocol over the f-channel and prove that any protocol that simulates it over the beeping channel blows up the round complexity by a factor of Ω(log n). Our lower bound technique may be of independent interest, as it essentially generalizes the popular fooling set technique by exploiting a "local" relaxation of combinatorial rectangles. Curiously, while this result shows the limitations of a noiseless channel, namely, the beeping channel, we are able to use it to show the limitations of the noisy version of many other channels. This includes the extensively studied single-hop radio network model with collisions-as-silence (CAS), which is equivalent to the f-channel with f(m) = 1 iff m = 1. In particular, our second and main result, obtained from the first, shows that converting CAS protocols to noise resilient ones may incur a large performance overhead, i.e., no constant rate interactive code exists. To this end, we design a CAS protocol and prove that any protocol that simulates it over the noisy CAS model with correlated stochastic noise, blows up the round complexity by a factor of Ω(log n). We mention that the Ω(log n) overhead in both our results is tight.

Cite as

Klim Efremenko, Gillat Kol, Dmitry Paramonov, and Raghuvansh R. Saxena. Noisy Radio Network Lower Bounds via Noiseless Beeping Lower Bounds. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 46:1-46:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{efremenko_et_al:LIPIcs.ITCS.2023.46,
  author =	{Efremenko, Klim and Kol, Gillat and Paramonov, Dmitry and Saxena, Raghuvansh R.},
  title =	{{Noisy Radio Network Lower Bounds via Noiseless Beeping Lower Bounds}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{46:1--46:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.46},
  URN =		{urn:nbn:de:0030-drops-175499},
  doi =		{10.4230/LIPIcs.ITCS.2023.46},
  annote =	{Keywords: Beeping Model, Radio Networks}
}
Document
Secret Sharing, Slice Formulas, and Monotone Real Circuits

Authors: Benny Applebaum, Amos Beimel, Oded Nir, Naty Peter, and Toniann Pitassi

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)


Abstract
A secret-sharing scheme allows to distribute a secret s among n parties such that only some predefined "authorized" sets of parties can reconstruct the secret s, and all other "unauthorized" sets learn nothing about s. For over 30 years, it was known that any (monotone) collection of authorized sets can be realized by a secret-sharing scheme whose shares are of size 2^{n-o(n)} and until recently no better scheme was known. In a recent breakthrough, Liu and Vaikuntanathan (STOC 2018) have reduced the share size to 2^{0.994n+o(n)}, and this was further improved by several follow-ups accumulating in an upper bound of 1.5^{n+o(n)} (Applebaum and Nir, CRYPTO 2021). Following these advances, it is natural to ask whether these new approaches can lead to a truly sub-exponential upper-bound of 2^{n^{1-ε}} for some constant ε > 0, or even all the way down to polynomial upper-bounds. In this paper, we relate this question to the complexity of computing monotone Boolean functions by monotone real circuits (MRCs) - a computational model that was introduced by Pudlák (J. Symb. Log., 1997) in the context of proof complexity. We introduce a new notion of "separable" MRCs that lies between monotone real circuits and monotone real formulas (MRFs). As our main results, we show that recent constructions of general secret-sharing schemes implicitly give rise to separable MRCs for general monotone functions of similar complexity, and that some monotone functions (in monotone NP) cannot be computed by sub-exponential size separable MRCs. Interestingly, it seems that proving similar lower-bounds for general MRCs is beyond the reach of current techniques. We use this connection to obtain lower-bounds against a natural family of secret-sharing schemes, as well as new non-trivial upper-bounds for MRCs. Specifically, we conclude that recent approaches for secret-sharing schemes cannot achieve sub-exponential share size and that every monotone function can be realized by an MRC (or even MRF) of complexity 1.5^{n+o(n)}. To the best of our knowledge, this is the first improvement over the trivial 2^{n-o(n)} upper-bound. Along the way, we show that the recent constructions of general secret-sharing schemes implicitly give rise to Boolean formulas over slice functions and prove that such formulas can be simulated by separable MRCs of similar size. On a conceptual level, our paper continues the rich line of study that relates the share size of secret-sharing schemes to monotone complexity measures.

Cite as

Benny Applebaum, Amos Beimel, Oded Nir, Naty Peter, and Toniann Pitassi. Secret Sharing, Slice Formulas, and Monotone Real Circuits. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 8:1-8:23, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{applebaum_et_al:LIPIcs.ITCS.2022.8,
  author =	{Applebaum, Benny and Beimel, Amos and Nir, Oded and Peter, Naty and Pitassi, Toniann},
  title =	{{Secret Sharing, Slice Formulas, and Monotone Real Circuits}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{8:1--8:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.8},
  URN =		{urn:nbn:de:0030-drops-156046},
  doi =		{10.4230/LIPIcs.ITCS.2022.8},
  annote =	{Keywords: Secret Sharing Schemes, Monotone Real Circuits}
}
Document
Computation over the Noisy Broadcast Channel with Malicious Parties

Authors: Klim Efremenko, Gillat Kol, Dmitry Paramonov, and Raghuvansh R. Saxena

Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)


Abstract
We study the n-party noisy broadcast channel with a constant fraction of malicious parties. Specifically, we assume that each non-malicious party holds an input bit, and communicates with the others in order to learn the input bits of all non-malicious parties. In each communication round, one of the parties broadcasts a bit to all other parties, and the bit received by each party is flipped with a fixed constant probability (independently for each recipient). How many rounds are needed? Assuming there are no malicious parties, Gallager gave an 𝒪(n log log n)-round protocol for the above problem, which was later shown to be optimal. This protocol, however, inherently breaks down in the presence of malicious parties. We present a novel n ⋅ 𝒪̃(√{log n})-round protocol, that solves this problem even when almost half of the parties are malicious. Our protocol uses a new type of error correcting code, which we call a locality sensitive code and which may be of independent interest. Roughly speaking, these codes map "close" messages to "close" codewords, while messages that are not close are mapped to codewords that are very far apart. We view our result as a first step towards a theory of property preserving interactive coding, i.e., interactive codes that preserve useful properties of the protocol being encoded. In our case, the naive protocol over the noiseless broadcast channel, where all the parties broadcast their input bit and output all the bits received, works even in the presence of malicious parties. Our simulation of this protocol, unlike Gallager’s, preserves this property of the original protocol.

Cite as

Klim Efremenko, Gillat Kol, Dmitry Paramonov, and Raghuvansh R. Saxena. Computation over the Noisy Broadcast Channel with Malicious Parties. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 82:1-82:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{efremenko_et_al:LIPIcs.ITCS.2021.82,
  author =	{Efremenko, Klim and Kol, Gillat and Paramonov, Dmitry and Saxena, Raghuvansh R.},
  title =	{{Computation over the Noisy Broadcast Channel with Malicious Parties}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{82:1--82:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-177-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{185},
  editor =	{Lee, James R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.82},
  URN =		{urn:nbn:de:0030-drops-136215},
  doi =		{10.4230/LIPIcs.ITCS.2021.82},
  annote =	{Keywords: Broadcast Network, Malicious Parties, Communication Complexity}
}
Document
Interactive Coding with Constant Round and Communication Blowup

Authors: Klim Efremenko, Elad Haramaty, and Yael Tauman Kalai

Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)


Abstract
The problem of constructing error-resilient interactive protocols was introduced in the seminal works of Schulman (FOCS 1992, STOC 1993). These works show how to convert any two-party interactive protocol into one that is resilient to constant-fraction of error, while blowing up the communication by only a constant factor. Since these seminal works, there have been many followup works which improve the error rate, the communication rate, and the computational efficiency. All these works only consider only an increase in communication complexity and did not consider an increase in round complexity. This work is the first one that considers the blowup of round complexity in noisy setting. While techniques from other papers can be easily adapted encode protocols with arbitrarily round complexity this coding schemes will lead to large(and usually unbounded) increase in round complexity of the protocol. In this work, we show how to convert any protocol Π, with no a priori known communication bound, into an error-resilient protocol Π', with comparable computational efficiency, that is resilient to constant fraction of adversarial error, while blowing up both the communication complexity and the round complexity by at most a constant factor. We consider the model where in each round each party may send a message of arbitrary length, where the length of the messages and the length of the protocol may be adaptive, and may depend on the private inputs of the parties and on previous communication. We consider the adversarial error model, where ε-fraction of the communication may be corrupted, where we allow each corruption to be an insertion or deletion (in addition to toggle). In addition, we try to minimize the blowup parameters: In particular, we construct such Π' with (1+Õ(ε^(1/4))) blowup in communication and O(1) blowup in rounds. We also show how to reduce the blowup in rounds at the expense of increasing the blowup in communication, and construct Π' where both the blowup in rounds and communication, approaches one (i.e., no blowup) as ε approaches zero. We give "evidence" that our parameters are "close to" optimal.

Cite as

Klim Efremenko, Elad Haramaty, and Yael Tauman Kalai. Interactive Coding with Constant Round and Communication Blowup. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 7:1-7:34, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{efremenko_et_al:LIPIcs.ITCS.2020.7,
  author =	{Efremenko, Klim and Haramaty, Elad and Kalai, Yael Tauman},
  title =	{{Interactive Coding with Constant Round and Communication Blowup}},
  booktitle =	{11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
  pages =	{7:1--7:34},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-134-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{151},
  editor =	{Vidick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.7},
  URN =		{urn:nbn:de:0030-drops-116927},
  doi =		{10.4230/LIPIcs.ITCS.2020.7},
  annote =	{Keywords: Interactive Coding, Round Complexity, Error Correcting Codes}
}
Document
On the Symmetries of and Equivalence Test for Design Polynomials

Authors: Nikhil Gupta and Chandan Saha

Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)


Abstract
In a Nisan-Wigderson design polynomial (in short, a design polynomial), every pair of monomials share a few common variables. A useful example of such a polynomial, introduced in [Neeraj Kayal et al., 2014], is the following: NW_{d,k}({x}) = sum_{h in F_d[z], deg(h) <= k}{ prod_{i=0}^{d-1}{x_{i, h(i)}}}, where d is a prime, F_d is the finite field with d elements, and k << d. The degree of the gcd of every pair of monomials in NW_{d,k} is at most k. For concreteness, we fix k = ceil[sqrt{d}]. The family of polynomials NW := {NW_{d,k} : d is a prime} and close variants of it have been used as hard explicit polynomial families in several recent arithmetic circuit lower bound proofs. But, unlike the permanent, very little is known about the various structural and algorithmic/complexity aspects of NW beyond the fact that NW in VNP. Is NW_{d,k} characterized by its symmetries? Is it circuit-testable, i.e., given a circuit C can we check efficiently if C computes NW_{d,k}? What is the complexity of equivalence test for NW, i.e., given black-box access to a f in F[{x}], can we check efficiently if there exists an invertible linear transformation A such that f = NW_{d,k}(A * {x})? Characterization of polynomials by their symmetries plays a central role in the geometric complexity theory program. Here, we answer the first two questions and partially answer the third. We show that NW_{d,k} is characterized by its group of symmetries over C, but not over R. We also show that NW_{d,k} is characterized by circuit identities which implies that NW_{d,k} is circuit-testable in randomized polynomial time. As another application of this characterization, we obtain the "flip theorem" for NW. We give an efficient equivalence test for NW in the case where the transformation A is a block-diagonal permutation-scaling matrix. The design of this algorithm is facilitated by an almost complete understanding of the group of symmetries of NW_{d,k}: We show that if A is in the group of symmetries of NW_{d,k} then A = D * P, where D and P are diagonal and permutation matrices respectively. This is proved by completely characterizing the Lie algebra of NW_{d,k}, and using an interplay between the Hessian of NW_{d,k} and the evaluation dimension.

Cite as

Nikhil Gupta and Chandan Saha. On the Symmetries of and Equivalence Test for Design Polynomials. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 53:1-53:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{gupta_et_al:LIPIcs.MFCS.2019.53,
  author =	{Gupta, Nikhil and Saha, Chandan},
  title =	{{On the Symmetries of and Equivalence Test for Design Polynomials}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{53:1--53:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.53},
  URN =		{urn:nbn:de:0030-drops-109979},
  doi =		{10.4230/LIPIcs.MFCS.2019.53},
  annote =	{Keywords: Nisan-Wigderson design polynomial, characterization by symmetries, Lie algebra, group of symmetries, circuit testability, flip theorem, equivalence test}
}
Document
Optimal Short-Circuit Resilient Formulas

Authors: Mark Braverman, Klim Efremenko, Ran Gelles, and Michael A. Yitayew

Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)


Abstract
We consider fault-tolerant boolean formulas in which the output of a faulty gate is short-circuited to one of the gate’s inputs. A recent result by Kalai et al. [FOCS 2012] converts any boolean formula into a resilient formula of polynomial size that works correctly if less than a fraction 1/6 of the gates (on every input-to-output path) are faulty. We improve the result of Kalai et al., and show how to efficiently fortify any boolean formula against a fraction 1/5 of short-circuit gates per path, with only a polynomial blowup in size. We additionally show that it is impossible to obtain formulas with higher resilience and sub-exponential growth in size. Towards our results, we consider interactive coding schemes when noiseless feedback is present; these produce resilient boolean formulas via a Karchmer-Wigderson relation. We develop a coding scheme that resists up to a fraction 1/5 of corrupted transmissions in each direction of the interactive channel. We further show that such a level of noise is maximal for coding schemes with sub-exponential blowup in communication. Our coding scheme takes a surprising inspiration from Blockchain technology.

Cite as

Mark Braverman, Klim Efremenko, Ran Gelles, and Michael A. Yitayew. Optimal Short-Circuit Resilient Formulas. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 10:1-10:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{braverman_et_al:LIPIcs.CCC.2019.10,
  author =	{Braverman, Mark and Efremenko, Klim and Gelles, Ran and Yitayew, Michael A.},
  title =	{{Optimal Short-Circuit Resilient Formulas}},
  booktitle =	{34th Computational Complexity Conference (CCC 2019)},
  pages =	{10:1--10:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-116-0},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{137},
  editor =	{Shpilka, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2019.10},
  URN =		{urn:nbn:de:0030-drops-108326},
  doi =		{10.4230/LIPIcs.CCC.2019.10},
  annote =	{Keywords: Circuit Complexity, Noise-Resilient Circuits, Interactive Coding, Coding Theory, Karchmer-Wigderson Games}
}
Document
Barriers for Rank Methods in Arithmetic Complexity

Authors: Klim Efremenko, Ankit Garg, Rafael Oliveira, and Avi Wigderson

Published in: LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)


Abstract
Arithmetic complexity, the study of the cost of computing polynomials via additions and multiplications, is considered (for many good reasons) simpler to understand than Boolean complexity, namely computing Boolean functions via logical gates. And indeed, we seem to have significantly more lower bound techniques and results in arithmetic complexity than in Boolean complexity. Despite many successes and rapid progress, however, foundational challenges, like proving super-polynomial lower bounds on circuit or formula size for explicit polynomials, or super-linear lower bounds on explicit 3-dimensional tensors, remain elusive. At the same time (and possibly for similar reasons), we have plenty more excuses, in the form of "barrier results" for failing to prove basic lower bounds in Boolean complexity than in arithmetic complexity. Efforts to find barriers to arithmetic lower bound techniques seem harder, and despite some attempts we have no excuses of similar quality for these failures in arithmetic complexity. This paper aims to add to this study. In this paper we address rank methods, which were long recognized as encompassing and abstracting almost all known arithmetic lower bounds to-date, including the most recent impressive successes. Rank methods (under the name of flattenings) are also in wide use in algebraic geometry for proving tensor rank and symmetric tensor rank lower bounds. Our main results are barriers to these methods. In particular, 1. Rank methods cannot prove better than (2^d)*n^(d/2) lower bound on the tensor rank of any d-dimensional tensor of side n. (In particular, they cannot prove super-linear, indeed even >8n tensor rank lower bounds for any 3-dimensional tensors.) 2. Rank methods cannot prove (d+1)n^(d/2) on the Waring rank of any n-variate polynomial of degree d. (In particular, they cannot prove such lower bounds on stronger models, including depth-3 circuits.) The proofs of these bounds use simple linear-algebraic arguments, leveraging connections between the symbolic rank of matrix polynomials and the usual rank of their evaluations. These techniques can perhaps be extended to barriers for other arithmetic models on which progress has halted. To see how these barrier results directly inform the state-of-art in arithmetic complexity we note the following. First, the bounds above nearly match the best explicit bounds we know for these models, hence offer an explanations why the rank methods got stuck there. Second, the bounds above are a far cry (quadratically away) from the true complexity (e.g. of random polynomials) in these models, which if achieved (by any methods), are known to imply super-polynomial formula lower bounds. We also explain the relation of our barrier results to other attempts, and in particular how they significantly differ from the recent attempts to find analogues of "natural proofs" for arithmetic complexity. Finally, we discuss the few arithmetic lower bound approaches which fall outside rank methods, and some natural directions our barriers suggest.

Cite as

Klim Efremenko, Ankit Garg, Rafael Oliveira, and Avi Wigderson. Barriers for Rank Methods in Arithmetic Complexity. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 1:1-1:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{efremenko_et_al:LIPIcs.ITCS.2018.1,
  author =	{Efremenko, Klim and Garg, Ankit and Oliveira, Rafael and Wigderson, Avi},
  title =	{{Barriers for Rank Methods in Arithmetic Complexity}},
  booktitle =	{9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
  pages =	{1:1--1:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-060-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{94},
  editor =	{Karlin, Anna R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.1},
  URN =		{urn:nbn:de:0030-drops-83506},
  doi =		{10.4230/LIPIcs.ITCS.2018.1},
  annote =	{Keywords: Lower Bounds, Barriers, Partial Derivatives, Flattenings, Algebraic Complexity}
}
Document
Communication with Partial Noiseless Feedback

Authors: Bernhard Haeupler, Pritish Kamath, and Ameya Velingker

Published in: LIPIcs, Volume 40, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)


Abstract
We introduce the notion of one-way communication schemes with partial noiseless feedback. In this setting, Alice wishes to communicate a message to Bob by using a communication scheme that involves sending a sequence of bits over a channel while receiving feedback bits from Bob for delta fraction of the transmissions. An adversary is allowed to corrupt up to a constant fraction of Alice's transmissions, while the feedback is always uncorrupted. Motivated by questions related to coding for interactive communication, we seek to determine the maximum error rate, as a function of 0 <= delta <= 1, such that Alice can send a message to Bob via some protocol with delta fraction of noiseless feedback. The case delta = 1 corresponds to full feedback, in which the result of Berlekamp ['64] implies that the maximum tolerable error rate is 1/3, while the case delta = 0 corresponds to no feedback, in which the maximum tolerable error rate is 1/4, achievable by use of a binary error-correcting code. In this work, we show that for any delta in (0,1] and gamma in [0, 1/3), there exists a randomized communication scheme with noiseless delta-feedback, such that the probability of miscommunication is low, as long as no more than a gamma fraction of the rounds are corrupted. Moreover, we show that for any delta in (0, 1] and gamma < f(delta), there exists a deterministic communication scheme with noiseless delta-feedback that always decodes correctly as long as no more than a gamma fraction of rounds are corrupted. Here f is a monotonically increasing, piecewise linear, continuous function with f(0) = 1/4 and f(1) = 1/3. Also, the rate of communication in both cases is constant (dependent on delta and gamma but independent of the input length).

Cite as

Bernhard Haeupler, Pritish Kamath, and Ameya Velingker. Communication with Partial Noiseless Feedback. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 881-897, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{haeupler_et_al:LIPIcs.APPROX-RANDOM.2015.881,
  author =	{Haeupler, Bernhard and Kamath, Pritish and Velingker, Ameya},
  title =	{{Communication with Partial Noiseless Feedback}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)},
  pages =	{881--897},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-89-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{40},
  editor =	{Garg, Naveen and Jansen, Klaus and Rao, Anup and Rolim, Jos\'{e} D. P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.881},
  URN =		{urn:nbn:de:0030-drops-53426},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2015.881},
  annote =	{Keywords: Communication with feedback, Interactive communication, Coding theory Digital}
}
Document
Nonclassical Polynomials as a Barrier to Polynomial Lower Bounds

Authors: Abhishek Bhowmick and Shachar Lovett

Published in: LIPIcs, Volume 33, 30th Conference on Computational Complexity (CCC 2015)


Abstract
The problem of constructing explicit functions which cannot be approximated by low degree polynomials has been extensively studied in computational complexity, motivated by applications in circuit lower bounds, pseudo-randomness, constructions of Ramsey graphs and locally decodable codes. Still, most of the known lower bounds become trivial for polynomials of super-logarithmic degree. Here, we suggest a new barrier explaining this phenomenon. We show that many of the existing lower bound proof techniques extend to nonclassical polynomials, an extension of classical polynomials which arose in higher order Fourier analysis. Moreover, these techniques are tight for nonclassical polynomials of logarithmic degree.

Cite as

Abhishek Bhowmick and Shachar Lovett. Nonclassical Polynomials as a Barrier to Polynomial Lower Bounds. In 30th Conference on Computational Complexity (CCC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 33, pp. 72-87, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{bhowmick_et_al:LIPIcs.CCC.2015.72,
  author =	{Bhowmick, Abhishek and Lovett, Shachar},
  title =	{{Nonclassical Polynomials as a Barrier to Polynomial Lower Bounds}},
  booktitle =	{30th Conference on Computational Complexity (CCC 2015)},
  pages =	{72--87},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-81-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{33},
  editor =	{Zuckerman, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2015.72},
  URN =		{urn:nbn:de:0030-drops-50491},
  doi =		{10.4230/LIPIcs.CCC.2015.72},
  annote =	{Keywords: nonclassical polynomials, polynomials, lower bounds, barrier}
}
Document
Strong Locally Testable Codes with Relaxed Local Decoders

Authors: Oded Goldreich, Tom Gur, and Ilan Komargodski

Published in: LIPIcs, Volume 33, 30th Conference on Computational Complexity (CCC 2015)


Abstract
Locally testable codes (LTCs) are error-correcting codes that admit very efficient codeword tests. An LTC is said to be strong if it has a proximity-oblivious tester; that is, a tester that makes only a constant number of queries and reject non-codewords with probability that depends solely on their distance from the code. Locally decodable codes (LDCs) are complimentary to LTCs. While the latter allow for highly efficient rejection of strings that are far from being codewords, LDCs allow for highly efficient recovery of individual bits of the information that is encoded in strings that are close to being codewords. While there are known constructions of strong-LTCs with nearly-linear length, the existence of a constant-query LDC with polynomial length is a major open problem. In an attempt to bypass this barrier, Ben-Sasson et al. (SICOMP 2006) introduced a natural relaxation of local decodability, called relaxed-LDCs. This notion requires local recovery of nearly all individual information-bits, yet allows for recovery-failure (but not error) on the rest. Ben-Sasson et al. constructed a constant-query relaxed-LDC with nearly-linear length (i.e., length k^(1 + alpha) for an arbitrarily small constant alpha>0, where k is the dimension of the code). This work focuses on obtaining strong testability and relaxed decodability simultaneously. We construct a family of binary linear codes of nearly-linear length that are both strong-LTCs (with one-sided error) and constant-query relaxed-LDCs. This improves upon the previously known constructions, which obtain either weak LTCs or require polynomial length. Our construction heavily relies on tensor codes and PCPs. In particular, we provide strong canonical PCPs of proximity for membership in any linear code with constant rate and relative distance. Loosely speaking, these are PCPs of proximity wherein the verifier is proximity oblivious (similarly to strong-LTCs and every valid statement has a unique canonical proof. Furthermore, the verifier is required to reject non-canonical proofs (even for valid statements). As an application, we improve the best known separation result between the complexity of decision and verification in the setting of property testing.

Cite as

Oded Goldreich, Tom Gur, and Ilan Komargodski. Strong Locally Testable Codes with Relaxed Local Decoders. In 30th Conference on Computational Complexity (CCC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 33, pp. 1-41, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{goldreich_et_al:LIPIcs.CCC.2015.1,
  author =	{Goldreich, Oded and Gur, Tom and Komargodski, Ilan},
  title =	{{Strong Locally Testable Codes with Relaxed Local Decoders}},
  booktitle =	{30th Conference on Computational Complexity (CCC 2015)},
  pages =	{1--41},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-81-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{33},
  editor =	{Zuckerman, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2015.1},
  URN =		{urn:nbn:de:0030-drops-50507},
  doi =		{10.4230/LIPIcs.CCC.2015.1},
  annote =	{Keywords: Locally Testable Codes, Locally Decodable Codes, PCPs of Proximity}
}
Document
Verifiable Stream Computation and Arthur–Merlin Communication

Authors: Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler, and Suresh Venkatasubramanian

Published in: LIPIcs, Volume 33, 30th Conference on Computational Complexity (CCC 2015)


Abstract
In the setting of streaming interactive proofs (SIPs), a client (verifier) needs to compute a given function on a massive stream of data, arriving online, but is unable to store even a small fraction of the data. It outsources the processing to a third party service (prover), but is unwilling to blindly trust answers returned by this service. Thus, the service cannot simply supply the desired answer; it must convince the verifier of its correctness via a short interaction after the stream has been seen. In this work we study "barely interactive" SIPs. Specifically, we show that two or three rounds of interaction suffice to solve several query problems - including Index, Median, Nearest Neighbor Search, Pattern Matching, and Range Counting - with polylogarithmic space and communication costs. Such efficiency with O(1) rounds of interaction was thought to be impossible based on previous work. On the other hand, we initiate a formal study of the limitations of constant-round SIPs by introducing a new hierarchy of communication models called Online Interactive Proofs (OIPs). The online nature of these models is analogous to the streaming restriction placed upon the verifier in an SIP. We give upper and lower bounds that (1) characterize, up to quadratic blowups, every finite level of the OIP hierarchy in terms of other well-known communication complexity classes, (2) separate the first four levels of the hierarchy, and (3) reveal that the hierarchy collapses to the fourth level. Our study of OIPs reveals marked contrasts and some parallels with the classic Turing Machine theory of interactive proofs, establishes limits on the power of existing techniques for developing constant-round SIPs, and provides a new characterization of (non-online) Arthur-Merlin communication in terms of an online model.

Cite as

Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler, and Suresh Venkatasubramanian. Verifiable Stream Computation and Arthur–Merlin Communication. In 30th Conference on Computational Complexity (CCC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 33, pp. 217-243, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{chakrabarti_et_al:LIPIcs.CCC.2015.217,
  author =	{Chakrabarti, Amit and Cormode, Graham and McGregor, Andrew and Thaler, Justin and Venkatasubramanian, Suresh},
  title =	{{Verifiable Stream Computation and Arthur–Merlin Communication}},
  booktitle =	{30th Conference on Computational Complexity (CCC 2015)},
  pages =	{217--243},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-81-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{33},
  editor =	{Zuckerman, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2015.217},
  URN =		{urn:nbn:de:0030-drops-50680},
  doi =		{10.4230/LIPIcs.CCC.2015.217},
  annote =	{Keywords: Arthur-Merlin communication complexity, streaming interactive proofs}
}
  • Refine by Author
  • 6 Efremenko, Klim
  • 3 Kol, Gillat
  • 3 Paramonov, Dmitry
  • 3 Saxena, Raghuvansh R.
  • 1 Applebaum, Benny
  • Show More...

  • Refine by Classification
  • 3 Theory of computation → Communication complexity
  • 2 Theory of computation → Computational complexity and cryptography
  • 2 Theory of computation → Interactive computation
  • 1 Theory of computation → Algebraic complexity theory
  • 1 Theory of computation → Circuit complexity
  • Show More...

  • Refine by Keyword
  • 3 Interactive Coding
  • 2 Error Correcting Codes
  • 2 Radio Networks
  • 1 Algebraic Complexity
  • 1 Arthur-Merlin communication complexity
  • Show More...

  • Refine by Type
  • 12 document

  • Refine by Publication Year
  • 4 2015
  • 2 2019
  • 2 2023
  • 1 2018
  • 1 2020
  • Show More...

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail