Publish in OALib Journal

ISSN: 2333-9721

APC: Only $99


Search Results: 1 - 10 of 709 matches for " Arkadev Chattopadhyay "
All listed articles are free for downloading (OA Articles)
Page 1 /709
Display every page Item
Multiparty Communication Complexity of Disjointness
Arkadev Chattopadhyay,Anil Ada
Computer Science , 2008,
Abstract: We obtain a lower bound of n^Omega(1) on the k-party randomized communication complexity of the Disjointness function in the `Number on the Forehead' model of multiparty communication when k is a constant. For k=o(loglog n), the bounds remain super-polylogarithmic i.e. (log n)^omega(1). The previous best lower bound for three players until recently was Omega(log n). Our bound separates the communication complexity classes NP^{CC}_k and BPP^{CC}_k for k=o(loglog n). Furthermore, by the results of Beame, Pitassi and Segerlind \cite{BPS07}, our bound implies proof size lower bounds for tree-like, degree k-1 threshold systems and superpolynomial size lower bounds for Lovasz-Schrijver proofs. Sherstov \cite{She07b} recently developed a novel technique to obtain lower bounds on two-party communication using the approximate polynomial degree of boolean functions. We obtain our results by extending his technique to the multi-party setting using ideas from Chattopadhyay \cite{Cha07}. A similar bound for Disjointness has been recently and independently obtained by Lee and Shraibman.
The Range of Topological Effects on Communication
Arkadev Chattopadhyay,Atri Rudra
Computer Science , 2015,
Abstract: We continue the study of communication cost of computing functions when inputs are distributed among $k$ processors, each of which is located at one vertex of a network/graph called a terminal. Every other node of the network also has a processor, with no input. The communication is point-to-point and the cost is the total number of bits exchanged by the protocol, in the worst case, on all edges. Chattopadhyay, Radhakrishnan and Rudra (FOCS'14) recently initiated a study of the effect of topology of the network on the total communication cost using tools from $L_1$ embeddings. Their techniques provided tight bounds for simple functions like Element-Distinctness (ED), which depend on the 1-median of the graph. This work addresses two other kinds of natural functions. We show that for a large class of natural functions like Set-Disjointness the communication cost is essentially $n$ times the cost of the optimal Steiner tree connecting the terminals. Further, we show for natural composed functions like $\text{ED} \circ \text{XOR}$ and $\text{XOR} \circ \text{ED}$, the naive protocols suggested by their definition is optimal for general networks. Interestingly, the bounds for these functions depend on more involved topological parameters that are a combination of Steiner tree and 1-median costs. To obtain our results, we use some new tools in addition to ones used in Chattopadhyay et. al. These include (i) viewing the communication constraints via a linear program; (ii) using tools from the theory of tree embeddings to prove topology sensitive direct sum results that handle the case of composed functions and (iii) representing the communication constraints of certain problems as a family of collection of multiway cuts, where each multiway cut simulates the hardness of computing the function on the star topology.
Factoring bivariate lacunary polynomials without heights
Arkadev Chattopadhyay,Bruno Grenet,Pascal Koiran,Natacha Portier,Yann Strozecki
Computer Science , 2012, DOI: 10.1145/2465506.2465932
Abstract: We present an algorithm which computes the multilinear factors of bivariate lacunary polynomials. It is based on a new Gap Theorem which allows to test whether a polynomial of the form P(X,X+1) is identically zero in time polynomial in the number of terms of P(X,Y). The algorithm we obtain is more elementary than the one by Kaltofen and Koiran (ISSAC'05) since it relies on the valuation of polynomials of the previous form instead of the height of the coefficients. As a result, it can be used to find some linear factors of bivariate lacunary polynomials over a field of large finite characteristic in probabilistic polynomial time.
Computing the multilinear factors of lacunary polynomials without heights
Arkadev Chattopadhyay,Bruno Grenet,Pascal Koiran,Natacha Portier,Yann Strozecki
Computer Science , 2013,
Abstract: We present a deterministic polynomial-time algorithm which computes the multilinear factors of multivariate lacunary polynomials over number fields. It is based on a new Gap theorem which allows to test whether $P(X)=\sum_{j=1}^k a_j X^{\alpha_j}(vX+t)^{\beta_j}(uX+w)^{\gamma_j}$ is identically zero in polynomial time. Previous algorithms for this task were based on Gap Theorems expressed in terms of the height of the coefficients. Our Gap Theorem is based on the valuation of the polynomial and is valid for any field of characteristic zero. As a consequence we obtain a faster and more elementary algorithm. Furthermore, we can partially extend the algorithm to other situations, such as absolute and approximate factorizations. We also give a version of our Gap Theorem valid for fields of large characteristic, and deduce a randomized polynomial-time algorithm to compute multilinear factors with at least three monomials of multivariate lacunary polynomials of finite fields of large characteristic. We provide $\mathsf{NP}$-hardness results to explain our inability to compute binomial factors.
Analytical Solution for Bending Stress Intensity Factor from Reissner’S Plate Theory  [PDF]
Lalitha Chattopadhyay
Engineering (ENG) , 2011, DOI: 10.4236/eng.2011.35060
Abstract: Plate-type structural members are commonly used in engineering applications like aircraft, ships nuclear reactors etc. These structural members often have cracks arising from manufacture or from material defects or stress concentrations. Designing a structure against fracture in service involves consideration of strength of the structure as a function of crack size, dimension and the applied load based on principles of fracture mechanics. In most of the engineering structures the plate thickness is generally small and in these cases though the classical plate theory has provided solutions, the neglect of transverse shear deformation leads to the limitation that only two conditions can be satisfied on any boundary whereas we have three physical boundary conditions on an edge of a plate. In this paper this incompatibility is eliminated by using Reissner plate theory where the transverse shear deformation is included and three physically natural boundary conditions of vanishing bending moment, twisting moment and transverse shear stress are satisfied at a free boundary. The problem of estimating the bending stress distribution in the neighbourhood of a crack located on a single line in an elastic plate of varying thickness subjected to out-of-plane moment applied along the edges of the plate is examined. Using Reissner’s plate theory and integral transform technique, the general formulae for the bending moment and twisting moment in an elastic plate containing cracks located on a single line are derived. The thickness depended solution is obtained in a closed form for the case in which there is a single crack in an infinite plate and the results are compared with those obtained from the literature.
Slow Structural Change in India: Is It Related to Rising Relative Price of Agriculture? A Partial Equilibrium Model  [PDF]
Subhasankar Chattopadhyay
Theoretical Economics Letters (TEL) , 2016, DOI: 10.4236/tel.2016.63044
Abstract: Economic growth across countries is associated with changes in the composition of sectoral output, employment and consumption structure, known as “structural change”. With high growth rates in the Indian economy in the post liberalization period, structural change is expected to be rapid. However, the share of the manufacturing sector has “crossed” over that of the agriculture only very recently from the supply side and yet to cross over from the demand side. Through a simple partial equilibrium model, this paper shows that such slow structural change may be linked to a secular rise in the relative price of agricultural goods in India.
Gold Nanoparticles: Acceptors for Efficient Energy Transfer from the Photoexcited Fluorophores  [PDF]
Debanjana Ghosh, Nitin Chattopadhyay
Optics and Photonics Journal (OPJ) , 2013, DOI: 10.4236/opj.2013.31004

The citrate reduction method of synthesis of gold nanoparticles (AuNP) is standardized with the assistance of instruments like spectrophotometer and TEM. A correlation has been developed between the particle diameter and the fractional concentration of the reductant. This enables one to assess the diameter of the AuNP to be synthesized, in advance, from the composition of the reaction mixture and the diameter of the synthesized particles can be confirmed simply from spectrophotometry. Further, it has been demonstrated that the synthesized AuNPs serve as excellent acceptors for a super-efficient energy transfer (ET) from the donor coumarin 153, leading to a quenching of fluorescence of the latter. The Stern-Volmer constants determined from the fluorescence lifetimes are in the range 107 - 109 mol-1·dm3 and are orders of magnitude higher than the normal photochemical quenching processes. The energy transfer efficiency increases radically with an increase in the size of the metal nanoparticle. The highly efficient energy transfer and the variation of the efficiency of the ET process with a variation of the particle size is ascribed to a large enhancement in the extinction coefficient and an increase in the spectral overlap between the plasmon absorption band of AuNPs and the fluorescence spectrum of C153 with an increase in the size of the nanoparticles. The impact of the work remains in providing a demonstration of a super quenching effect of the AuNPs and projects that they can be exploited for developing biosensors with high degree of sensitivity, if tagged to the biomacromolecules.

Protein Mediated Silica Particles with pH Controlled Porosity and Morphology  [PDF]
Shilpi Show, Brajadulal Chattopadhyay
Advances in Microbiology (AiM) , 2016, DOI: 10.4236/aim.2016.614093
Abstract: Background: The silica leaching activity of some of the mystifying non-pathogenic BKH1 bacteria present in the cluster of hot springs (temperatures range 35°C - 80°C) at Bakreshwar (West Bengal, India, 23°52'48\"N; 87°22'40\"N) has provided some significant advancements in the field of nanotechnology. The present investigation was designed to synthesis the silica particles using bioremediase protein at different pH conditions. Methods: A secretary bacterial protein bioremediase (UniProt Knowledgebase Accession Number P86277) isolated from a thermophilic non-pathogenic bacterium BKH1 (GenBank Accession No. FJ177512) has been used to synthesis the silica particles at different pH conditions (pH at 3.0, 5.0, 8.0, 10.0, and 12.0 respectively). The silica particles were synthesized by the action of bioremediase protein on Tetra-ethyl-orthosilicate (TEOS) under ambient condition. Morphological and compositional studies of the biosynthesized silica particles were characterized by Field emission scanning electron microscope (FE-SEM) equipped with Energy dispersive X-ray analyser (EDX). Results: The Fourier transformed infra-red (FTIR) spectroscopic analysis confirmed the nature as well as occurrence of several functional groups surrounded on the silica particles. The amorphous nature of the prepared silica particles was confirmed by X-ray diffractometer (XRD) study. The Zeta potential (ζ) study revealed the stability of silica particles in neutral pH environment. The Brunauer-Emmett-Teller (BET) surface area measurement confirmed the porosity variation in all biosynthesized silica particles prepared at different pH conditions. Raman spectra analytically depend on their respective specific surface (BET) area. Thermogravimetry tool was used to monitor the effects of the thermal treatment on the surface properties of all the samples. Conclusions: The method for the synthesis of silica particles at different pH condition using the protein bioremediase has a special implication as it is an environmentally benign, cost-effective and facile technique which may have conceivable application in chromatographic packing. In addition, controlling of size as well as porosity of the silica particles can be achievable by pH as an only variable.
Statistics of Projected Motion in One Dimension of a D-Dimensional Random Walker  [PDF]
Jayeeta Chattopadhyay, Muktish Acharyya
Applied Mathematics (AM) , 2018, DOI: 10.4236/am.2018.96042
We are studying the motion of a random walker in generalised d-dimensional continuum with unit step length (up to 10 dimensions) and its projected one dimensional motion numerically. The motion of a random walker in lattice or continuum is well studied in statistical physics but what will be the statistics of projected one dimensional motion of higher dimensional random walker is yet to be explored. Here in this paper, by addressing this particular type of problem, it shows that the projected motion is diffusive irrespective of any dimension; however, the diffusion rate is changing inversely with dimensions. As a consequence, it can be predicted that for the one dimensional projected motion of infinite dimensional random walk, the diffusion rate will be zero. This is an interesting result, at least pedagogically, which implies that though in infinite dimensions there is diffusion, its one dimensional projection is motionless. At the end of the discussion we are able to make a good comparison between projected one dimensional motion of generalised d-dimensional random walk with unit step length and pure one dimensional random walk with random step length varying uniformly between -h to h where h is a “step length renormalizing factor”.
A Simple Model of Currency Notes Withdrawal  [PDF]
Siddhartha Chattopadhyay, Sohini Sahu
Theoretical Economics Letters (TEL) , 2018, DOI: 10.4236/tel.2018.814198
Abstract: In the backdrop of the demonetization move by the Government of India, this paper proposes a model of optimal currency holding when there is a possibility of currency withdrawal. Our results indicate that if the perceived probability of withdrawal of higher denomination currency is very high, then agents would eventually hold cash in lower denomination currency only, thereby making the higher currency notes redundant. Thus, one of the targets of demonetization, which is less holding of higher currency notes, can be achieved without actually implementing demonetization.
Page 1 /709
Display every page Item

Copyright © 2008-2017 Open Access Library. All rights reserved.