The Experts below are selected from a list of 1635 Experts worldwide ranked by ideXlab platform

Klim Efremenko - One of the best experts on this subject based on the ideXlab platform.

  • list and unique coding for interactive communication in the presence of adversarial noise
    Foundations of Computer Science, 2014
    Co-Authors: Mark Braverman, Klim Efremenko
    Abstract:

    In this paper we extend the notion of list-decoding to the setting of interactive communication and study its limits. In particular, we show that any protocol can be encoded, with a constant rate, into a list-decodable protocol which is resilient to a noise rate of up to 1/2--e, and that this is tight. Using our list-decodable construction, we study a more nuanced model of noise where the adversary can corrupt up to a fraction α Alice's communication and up to a fraction β of Bob's communication. We use list-decoding in order to fully characterize the region RU of pairs (α β) for which unique decoding with a constant rate is possible. The region RU turns out to be quite unusual in its shape. In particular, it is bounded by a piecewise-Differentiable Curve with infinitely many pieces. We show that outside this region, the rate must be exponential. This suggests that in some error regimes, list-decoding is necessary for optimal unique decoding. We also consider the setting where only one party of the communication must output the correct answer. We precisely characterize the region of all pairs (α β) for which one-sided unique decoding is possible in a way that Alice will output the correct answer.

Mark Braverman - One of the best experts on this subject based on the ideXlab platform.

  • list and unique coding for interactive communication in the presence of adversarial noise
    Foundations of Computer Science, 2014
    Co-Authors: Mark Braverman, Klim Efremenko
    Abstract:

    In this paper we extend the notion of list-decoding to the setting of interactive communication and study its limits. In particular, we show that any protocol can be encoded, with a constant rate, into a list-decodable protocol which is resilient to a noise rate of up to 1/2--e, and that this is tight. Using our list-decodable construction, we study a more nuanced model of noise where the adversary can corrupt up to a fraction α Alice's communication and up to a fraction β of Bob's communication. We use list-decoding in order to fully characterize the region RU of pairs (α β) for which unique decoding with a constant rate is possible. The region RU turns out to be quite unusual in its shape. In particular, it is bounded by a piecewise-Differentiable Curve with infinitely many pieces. We show that outside this region, the rate must be exponential. This suggests that in some error regimes, list-decoding is necessary for optimal unique decoding. We also consider the setting where only one party of the communication must output the correct answer. We precisely characterize the region of all pairs (α β) for which one-sided unique decoding is possible in a way that Alice will output the correct answer.

Efremenko K - One of the best experts on this subject based on the ideXlab platform.

  • LIST and unique coding for interactive communication in the presence of adversarial noise
    'Society for Industrial & Applied Mathematics (SIAM)', 2017
    Co-Authors: Braverman Mark, Efremenko K
    Abstract:

    In this paper, we extend the notion of list decoding to the setting of interactive communication and study its limits. In particular, we show that any protocol can be encoded, with a constant rate, into a list-decodable protocol which is resilient to a noise rate of up to 1/2 - ϵ, and that this is tight. Using our list-decodable construction, we study a more nuanced model of noise where the adversary can corrupt up to a fraction α of Alice's communication and up to a fraction β of Bob's communication. We use list decoding to characterize fully the region RU of pairs (α, β) for which unique decoding with a constant rate is possible. The region RU turns out to be quite unusual in its shape. In particular, it is bounded by a piecewise-Differentiable Curve with infinitely many pieces. We show that outside this region the rate must be exponential. This suggests that in some error regimes, list decoding is necessary for optimal unique decoding. We also consider the setting where only one party of the communication must output the correct answer. We precisely characterize the region of all pairs (α, β) for which one-sided unique decoding is possible in such a way that Alice will output the correct answer

Braverman Mark - One of the best experts on this subject based on the ideXlab platform.

  • LIST and unique coding for interactive communication in the presence of adversarial noise
    'Society for Industrial & Applied Mathematics (SIAM)', 2017
    Co-Authors: Braverman Mark, Efremenko K
    Abstract:

    In this paper, we extend the notion of list decoding to the setting of interactive communication and study its limits. In particular, we show that any protocol can be encoded, with a constant rate, into a list-decodable protocol which is resilient to a noise rate of up to 1/2 - ϵ, and that this is tight. Using our list-decodable construction, we study a more nuanced model of noise where the adversary can corrupt up to a fraction α of Alice's communication and up to a fraction β of Bob's communication. We use list decoding to characterize fully the region RU of pairs (α, β) for which unique decoding with a constant rate is possible. The region RU turns out to be quite unusual in its shape. In particular, it is bounded by a piecewise-Differentiable Curve with infinitely many pieces. We show that outside this region the rate must be exponential. This suggests that in some error regimes, list decoding is necessary for optimal unique decoding. We also consider the setting where only one party of the communication must output the correct answer. We precisely characterize the region of all pairs (α, β) for which one-sided unique decoding is possible in such a way that Alice will output the correct answer

Tommei G. - One of the best experts on this subject based on the ideXlab platform.

  • A NEW WAY OF THINKING ABOUT IMPACT MONITORING OF NEAR-EARTHOBJECTS
    2019
    Co-Authors: Tommei G.
    Abstract:

    An asteroid just been discovered has a strongly undeter-mined orbit, being weakly constrained by the few avail-able astrometric observations, and there is a set of possi-ble orbits, all compatible with the observations, forminga Confidence Region (CR) in the 6-dimensional orbitalelements space. The goal of Impact Monitoring (IM) isto understand whether the CR contains subsets of initialconditions leading to a collision with the Earth in the fu-ture (Virtual Impactors, VIs) and to estimate the ImpactProbability (IP). Once defined the CR, the crucial stepsare the sampling of the uncertainty region, the propaga-tion of the so called Virtual Asteroids (VAs) searchingfor VIs and the computation of IP. Two automatic sys-tems, CLOMON2 (at University of Pisa/SpaceDyS/ESA-NEOCC) and Sentry (at JPL/NASA), have been devel-oped for this purpose. Both generate VAs by applying a1-dimensional sampling of the CR based upon the LineOf Variations (LOV), that is a Differentiable Curve rep-resenting a kind of spine of the uncertainty region. TheLOV method is very useful when the CR is elongated andthin, but this is not the case when the observed arc is veryshort: the uncertainty results to be wide in at least twodirections and the LOV is not a reliable representativeof the entire region. Unfortunately, this is precisely thecase of very small asteroids observed only shortly beforea close approach or an impact with the Earth (imminentimpactors). The problem has been faced recently andthree systems were developed, SCOUT (at JPL/NASA),NEORANGER (at University of Helsinki) and NEOScan(at University of Pisa/SpaceDyS): we will focus on thelatter. NEOScan consults the NEO Confirmation Page(NEOCP) of the Minor Planet Center (MPC) every twominutes, extracting data and running the algorithms basedon the Admissible Region (AR), a tool widely used alsoin the space debris orbit determination. Once an objectgoes away from the NEOCP obtaining a designation, theIM systems switch to “classical” 1-d algorithms. In thisprocedure, essentially dictated by the rules of the MPC,there is a flaw, in the sense that there are objects, witha very well-defined orbit, remaining on the NEOCP, and,on the contrary, there exist designated objects with a greatuncertainty. Thus, there are a certain number of cases thatare not properly processed. In this paper, after a reviewof the IM algorithms developed at the University of Pisa, we will present the idea of a new automatic system capa-ble, starting from the astrometric observations, to decidewhat is the right algorithm in order to reach reasonableresults for each kind of orbit