15,279 research outputs found
Memory-Sample Lower Bounds for Learning Parity with Noise
No full textIn this work, we show, for the well-studied problem of learning parity under noise, where a learner tries to learn x = (x₁,…,x_n) ∈ {0,1}ⁿ from a stream of random linear equations over ₂ that are correct with probability 1/2+ε and flipped with probability 1/2-ε (0 < ε < 1/2), that any learning algorithm requires either a memory of size Ω(n²/ε) or an exponential number of samples.
In fact, we study memory-sample lower bounds for a large class of learning problems, as characterized by [Garg et al., 2018], when the samples are noisy. A matrix M: A × X → {-1,1} corresponds to the following learning problem with error parameter ε: an unknown element x ∈ X is chosen uniformly at random. A learner tries to learn x from a stream of samples, (a₁, b₁), (a₂, b₂) …, where for every i, a_i ∈ A is chosen uniformly at random and b_i = M(a_i,x) with probability 1/2+ε and b_i = -M(a_i,x) with probability 1/2-ε (0 < ε < 1/2). Assume that k,, r are such that any submatrix of M of at least 2^{-k} ⋅ |A| rows and at least 2^{-} ⋅ |X| columns, has a bias of at most 2^{-r}. We show that any learning algorithm for the learning problem corresponding to M, with error parameter ε, requires either a memory of size at least Ω((k⋅)/ε), or at least 2^{Ω(r)} samples. The result holds even if the learner has an exponentially small success probability (of 2^{-Ω(r)}). In particular, this shows that for a large class of learning problems, same as those in [Garg et al., 2018], any learning algorithm requires either a memory of size at least Ω(((log|X|)⋅(log|A|))/ε) or an exponential number of noisy samples.
Our proof is based on adapting the arguments in [Ran Raz, 2017; Garg et al., 2018] to the noisy case
Inequivalent Leggett-Garg inequalities
No full textIt remains an open question how a realist view of the macroscopic world emerges from a quantum formalism. For testing the macrorealism in the quantum domain, an interesting approach was put forward by Leggett and Garg in 1985, by formulating a suitable inequality valid for any macrorealistic theory. Recently, by following the Wigner idea of local realist inequality, a probabilistic version of standard Leggett-Garg inequalities has also been proposed. While the Wigner form of local realist inequalities is equivalent to the two-party, two-measurements and two-outcomes CHSH inequalities, in this paper we provide a generic proof to demonstrate that the Wigner form of Leggett-Garg inequalities is not only inequivalent to the standard ones, but also stronger than the latter. This is demonstrated by quantifying the amount of disturbance caused by a priori measurement to the subsequent measurements. In this connection, the relation between LGIs and another formulation of macrorealism known as no-signaling in time is examined
Entropic Leggett–Garg inequality in neutrinos and B(K) meson systems
No full textAbstract Entropic Leggett–Garg inequality is studied in systems like neutrinos in the context of two and three flavor neutrino oscillations and in neutral Bd , Bs and K mesons. The neutrino dynamics is described with the matter effect taken into consideration. For the decohering B / K meson systems, the effect of decoherence and CP violation have also been taken into account, using the techniques of open quantum systems. Enhancement in the violation with increase in the number of measurements has been found, in consistency with findings in spin-s systems. The effect of decoherence is found to bring the deficit parameter D[n] closer to its classical value zero, as expected. The violation of entropic Leggett–Garg inequality lasts for a much longer time in K meson system than in Bd and Bs systems
sj-pdf-1-lrt-10.1177_14771535211063624 – Supplemental Material for Analysis, evaluation and integration of modular natural illumination system using a rectangular Fresnel lens for high performance
No full textSupplemental Material, sj-pdf-1-lrt-10.1177_14771535211063624 for Analysis, evaluation and integration of modular natural illumination system using a rectangular Fresnel lens for high performance by H Garg, DS Bisht, K Sharma, V Kumar, K Kaur and N Garg in Lighting Research & Technology</p
Radical Sylvester-Gallai Theorem for Tuples of Quadratics
No full textWe prove a higher codimensional radical Sylvester-Gallai type theorem for quadratic polynomials, simultaneously generalizing [Hansen, 1965; Shpilka, 2020]. Hansen’s theorem is a high-dimensional version of the classical Sylvester-Gallai theorem in which the incidence condition is given by high-dimensional flats instead of lines. We generalize Hansen’s theorem to the setting of quadratic forms in a polynomial ring, where the incidence condition is given by radical membership in a high-codimensional ideal. Our main theorem is also a generalization of the quadratic Sylvester-Gallai Theorem of [Shpilka, 2020].
Our work is the first to prove a radical Sylvester-Gallai type theorem for arbitrary codimension k ≥ 2, whereas previous works [Shpilka, 2020; Shir Peleg and Amir Shpilka, 2020; Shir Peleg and Amir Shpilka, 2021; Garg et al., 2022] considered the case of codimension 2 ideals. Our techniques combine algebraic geometric and combinatorial arguments. A key ingredient is a structural result for ideals generated by a constant number of quadratics, showing that such ideals must be radical whenever the quadratic forms are far apart. Using the wide algebras defined in [Garg et al., 2022], combined with results about integral ring extensions and dimension theory, we develop new techniques for studying such ideals generated by quadratic forms. One advantage of our approach is that it does not need the finer classification theorems for codimension 2 complete intersection of quadratics proved in [Shpilka, 2020; Garg et al., 2022]
Brief Announcement: Applying Predicate Detection to the Stable Marriage Problem
No full textWe show that many techniques developed in the context of predicate detection are applicable to the stable marriage problem. The standard Gale-Shapley algorithm can be derived as a special case of detecting linear predicates. We also show that techniques in computation slicing can be used to represent the set of all constrained stable matchings
Antipowers in Uniform Morphic Words and the Fibonacci Word
No full textFici, Restivo, Silva, and Zamboni define a -antipower to be a word
composed of pairwise distinct, concatenated words of equal length. Berger
and Defant conjecture that for any sufficiently well-behaved aperiodic morphic
word , there exists a constant such that for any and any index ,
a -antipower with block length at most starts at the th position of
. They prove their conjecture in the case of binary words, and we extend
their result to alphabets of arbitrary finite size and characterize those words
for which the result does not hold. We also prove their conjecture in the
specific case of the Fibonacci word
Recommended from our members
Time-Space Tradeoffs for Distinguishing Distributions and Applications to Security of Goldreich’s PRG
No full textIn this work, we establish lower-bounds against memory bounded algorithms for distinguishing between natural pairs of related distributions from samples that arrive in a streaming setting.
Our first result applies to the problem of distinguishing the uniform distribution on {0,1}ⁿ from uniform distribution on some unknown linear subspace of {0,1}ⁿ. As a specific corollary, we show that any algorithm that distinguishes between uniform distribution on {0,1}ⁿ and uniform distribution on an n/2-dimensional linear subspace of {0,1}ⁿ with non-negligible advantage needs 2^Ω(n) samples or Ω(n²) memory (tight up to constants in the exponent).
Our second result applies to distinguishing outputs of Goldreich’s local pseudorandom generator from the uniform distribution on the output domain. Specifically, Goldreich’s pseudorandom generator G fixes a predicate P:{0,1}^k → {0,1} and a collection of subsets S₁, S₂, …, S_m ⊆ [n] of size k. For any seed x ∈ {0,1}ⁿ, it outputs P(x_S₁), P(x_S₂), …, P(x_{S_m}) where x_{S_i} is the projection of x to the coordinates in S_i. We prove that whenever P is t-resilient (all non-zero Fourier coefficients of (-1)^P are of degree t or higher), then no algorithm, with < n^ε memory, can distinguish the output of G from the uniform distribution on {0,1}^m with a large inverse polynomial advantage, for stretch m ≤ (n/t) ^{(1-ε)/36 ⋅ t} (barring some restrictions on k). The lower bound holds in the streaming model where at each time step i, S_i ⊆ [n] is a randomly chosen (ordered) subset of size k and the distinguisher sees either P(x_{S_i}) or a uniformly random bit along with S_i.
An important implication of our second result is the security of Goldreich’s generator with super linear stretch (in the streaming model), against memory-bounded adversaries, whenever the predicate P satisfies the necessary condition of t-resiliency identified in various prior works.
Our proof builds on the recently developed machinery for proving time-space trade-offs (Raz 2016 and follow-ups). Our key technical contribution is to adapt this machinery to work for distinguishing problems in contrast to prior works on similar results for search/learning problems
K*(892)± resonance with the ALICE detector at LHC
No full textK*(892)± resonance with the ALICE detector at LHC
Author: Kunal Garg
PhD Cycle XXXI, University of Catania
It has been established that ultra-relativistic heavy-ion collisions produce a hot and dense QCD system which behaves like a perfect fluid. The study of the Quark Gluon Plasma created in these collisions is important to understand the cosmic evolution of our Universe. The study of strange hadronic resonances in pp collisions contributes to the study of strangeness production in small systems. Usually, measurements in pp collisions constitute a reference for the study in larger colliding systems and provide constraints for tuning QCD-inspired event generators and then to test specific aspects of QCD in the non-perturbative sector. However recent observations at the LHC have shown striking similarities between Pb-Pb collisions and high-multiplicity p-Pb and pp collisions. In the elementary collisions a large variation of the characteristics of the event and of the strange particle production rate has been observed as a function of the charged particle multiplicity density. In particular it has been observed as particle production depends only from the event multiplicity and it is independent of the system size and collision energy.
This thesis reports about first measurement of K^{*}(892)^{\pm} in pp collisions at \sqrt{s} = 13 TeV in inelastic pp collisions and in different charged particle multiplicity classes. In particular the transverse momentum (p_{T}) spectrum, the integrated yield, the mean p_{T} and the ratio to stable hadrons as pions and kaons have been measured. Moreover the K^{*}(892)^{0} p_{T} spectrum in inelastic pp collisions at the same energy has been also measured. Similar results have been obtained for charged and neutral K^{*}. The K*(892)± p_{T} spectrum has been compared to the predictions of some event generators as PYTHIA6, PYTHIA8 and EPOS-LHC. Furthermore, the comparison of the p_{T} spectrum with the one obtained at different energies has shown a hardening of the spectra with increasing energy of the collisions.
Increase of the K*(892)± yield and mean p_{T} when growing the event multiplicity, confirms the independence of the particle yields from the collision system or energy. From the distribution of the K^{*}/K ratio as a function of the charged particle multiplicity, a hint of suppression of the K* production has been observed in high multiplicity pp collisions. This in an analogy to the K^{*}/K results in heavy-ion collisions, is consistent with the presence of re-scattering effects in an hadronic phase in high multiplicity pp collisions
Recommended from our members
Time-Space Lower Bounds for Two-Pass Learning
No full textA line of recent works showed that for a large class of learning problems, any learning algorithm requires either super-linear memory size or a super-polynomial number of samples [Raz, 2016; Kol et al., 2017; Raz, 2017; Moshkovitz and Moshkovitz, 2018; Beame et al., 2018; Garg et al., 2018]. For example, any algorithm for learning parities of size n requires either a memory of size Omega(n^{2}) or an exponential number of samples [Raz, 2016].
All these works modeled the learner as a one-pass branching program, allowing only one pass over the stream of samples. In this work, we prove the first memory-samples lower bounds (with a super-linear lower bound on the memory size and super-polynomial lower bound on the number of samples) when the learner is allowed two passes over the stream of samples. For example, we prove that any two-pass algorithm for learning parities of size n requires either a memory of size Omega(n^{1.5}) or at least 2^{Omega(sqrt{n})} samples.
More generally, a matrix M: A x X - > {-1,1} corresponds to the following learning problem: An unknown element x in X is chosen uniformly at random. A learner tries to learn x from a stream of samples, (a_1, b_1), (a_2, b_2) ..., where for every i, a_i in A is chosen uniformly at random and b_i = M(a_i,x).
Assume that k,l, r are such that any submatrix of M of at least 2^{-k} * |A| rows and at least 2^{-l} * |X| columns, has a bias of at most 2^{-r}. We show that any two-pass learning algorithm for the learning problem corresponding to M requires either a memory of size at least Omega (k * min{k,sqrt{l}}), or at least 2^{Omega(min{k,sqrt{l},r})} samples
- …
