188,097 research outputs found
Clustering Permutations: New Techniques with Streaming Applications
No full textWe study the classical metric k-median clustering problem over a set of input rankings (i.e., permutations), which has myriad applications, from social-choice theory to web search and databases. A folklore algorithm provides a 2-approximate solution in polynomial time for all k = O(1), and works irrespective of the underlying distance measure, so long it is a metric; however, going below the 2-factor is a notorious challenge. We consider the Ulam distance, a variant of the well-known edit-distance metric, where strings are restricted to be permutations. For this metric, Chakraborty, Das, and Krauthgamer [SODA, 2021] provided a (2-δ)-approximation algorithm for k = 1, where δ≈ 2^{-40}.
Our primary contribution is a new algorithmic framework for clustering a set of permutations. Our first result is a 1.999-approximation algorithm for the metric k-median problem under the Ulam metric, that runs in time (k log (nd))^{O(k)} nd³ for an input consisting of n permutations over [d]. In fact, our framework is powerful enough to extend this result to the streaming model (where the n input permutations arrive one by one) using only polylogarithmic (in n) space. Additionally, we show that similar results can be obtained even in the presence of outliers, which is presumably a more difficult problem
Science and technology for the people? On the framing of innovation in policy discourses in India and in EU
No full textIn 2010 both India and Europe launched new strategies focused on innovation, for economic growth and for addressing societal challenges: the Decade of Innovation from the Indian Government and the Innovation Union from the European Union. This piqued our interest in investigating how these two political entities have envisioned the concept of innovation, particularly in studying and comparing how they have focused on people, both as final beneficiaries (and thus principal legitimisers) of policy actions, and as actors themselves in the innovation process. Per contra we found, in institutional documents, very different descriptions of how to adequately realise citizens\u27 involvement, spanning from the abiding reference to people\u27s inclusion in the Indian case to the varied discourses on public engagement in EU, down to the passive role accorded to citizens in some Expert Groups reports. The comparison between the understandings of innovation (and innovators) in the two contexts can enlarge and refine the argumentative and metaphoric repertoire of science communicators. Further, it can form the basis of a mature and shared debate on the role that knowledge production and innovation policies can and should play in the public governance of science and technology
Appropriate Similarity Measures for Author Cocitation Analysis
No full textWe provide a number of new insights into the methodological discussion about author cocitation analysis. We first argue that the use of the Pearson correlation for measuring the similarity between authors’ cocitation profiles is not very satisfactory. We then discuss what kind of similarity measures may be used as an alternative to the Pearson correlation. We consider three similarity measures in particular. One is the well-known cosine. The other two similarity measures have not been used before in the bibliometric literature. Finally, we show by means of an example that our findings have a high practical relevance.information science;Pearson correlation;cosine;similarity measure;author cocitation analysis
Assessment of Thermal Performance of Semicircular Fin under Forced Air Convection: Application to Air-preheater
No full textAbstractThe performance of semi-circular fins subjected to forced convection has been studied analytically. The expression for its efficiency has been derived by solving a two-dimensional thermal energy balance equation and the computed efficiency has been compared with an equal volume circular fin. Under the operating conditions studied, the thermal efficiency of the semi-circular fin exceeded that of its circular counterpart. The effects of various parameters on the heat transfer coefficient and the exit air temperature have been determined for semi-circular finned air preheater. The heat transfer coefficient under forced air convection has been found to increase with an increment of the air velocity and reduction in the tube pitch, pipe size and fin spacing. The extent of air-preheats increases with an increase in pipe size and decrease in fin spacing, air velocity and tube pitch. Due to higher thermal performance of semi-circular fins compared to circular fins under identical conditions, improved energy efficiency can be achieved in air pre-heater
"Closing the R&D Gap, Evaluating the Sources of R&D Spending"
No full textBoth spending and tax policies have been implemented in the United States with the goal of stimulating private sector research and development (R&D). Karier questions whether current R&D policy, especially the research and experimentation tax credit, can contribute to closing the gap between nondefense expenditures on R&D in the United States and such expenditures in other countries, such as Japan and Germany. He also explores possible changes to our current R&D policy to make it more effective.
Supplementary_material – Supplemental material for Abrupt climate change at ~2800 yr BP evidenced by a stalagmite record from peninsular India
No full textSupplemental material, Supplementary_material for Abrupt climate change at ~2800 yr BP evidenced by a stalagmite record from peninsular India by Nitesh Sinha, Naveen Gandhi, S Chakraborty, R Krishnan, MG Yadava and R Ramesh in The Holocene</p
Improved Bounds on Fourier Entropy and Min-Entropy
No full textGiven a Boolean function f:{-1,1}ⁿ→ {-1,1}, define the Fourier distribution to be the distribution on subsets of [n], where each S ⊆ [n] is sampled with probability f̂(S)². The Fourier Entropy-Influence (FEI) conjecture of Friedgut and Kalai [E. Friedgut and G. Kalai, 1996] seeks to relate two fundamental measures associated with the Fourier distribution: does there exist a universal constant C>0 such that ℍ(f̂²)≤ C⋅ Inf(f), where ℍ(f̂²) is the Shannon entropy of the Fourier distribution of f and Inf(f) is the total influence of f?
In this paper we present three new contributions towards the FEI conjecture:
ii) Our first contribution shows that ℍ(f̂²) ≤ 2⋅ aUC^⊕(f), where aUC^⊕(f) is the average unambiguous parity-certificate complexity of f. This improves upon several bounds shown by Chakraborty et al. [S. Chakraborty et al., 2016]. We further improve this bound for unambiguous DNFs.
iii) We next consider the weaker Fourier Min-entropy-Influence (FMEI) conjecture posed by O'Donnell and others [R. O'Donnell et al., 2011; R. O'Donnell, 2014] which asks if ℍ_{∞}(f̂²) ≤ C⋅ Inf(f), where ℍ_{∞}(f̂²) is the min-entropy of the Fourier distribution. We show ℍ_{∞}(f̂²) ≤ 2⋅?_{min}^⊕(f), where ?_{min}^⊕(f) is the minimum parity certificate complexity of f. We also show that for all ε ≥ 0, we have ℍ_{∞}(f̂²) ≤ 2log (‖f̂‖_{1,ε}/(1-ε)), where ‖f̂‖_{1,ε} is the approximate spectral norm of f. As a corollary, we verify the FMEI conjecture for the class of read-k DNFs (for constant k).
iv) Our third contribution is to better understand implications of the FEI conjecture for the structure of polynomials that 1/3-approximate a Boolean function on the Boolean cube. We pose a conjecture: no flat polynomial (whose non-zero Fourier coefficients have the same magnitude) of degree d and sparsity 2^ω(d) can 1/3-approximate a Boolean function. This conjecture is known to be true assuming FEI and we prove the conjecture unconditionally (i.e., without assuming the FEI conjecture) for a class of polynomials. We discuss an intriguing connection between our conjecture and the constant for the Bohnenblust-Hille inequality, which has been extensively studied in functional analysis
Going Beyond Counting First Authors in Author Co-citation Analysis
No full textThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
Application of passive microwave and optical signatures to monitor vegetation submerging due to floods
No full textStrongly resolved diffraction resonances in positronium formation from C in forward direction
No full textInternational audiencePositronium formation by capturing from various levels of C within 10 degrees around the incoming positron direction is calculated. Results indicate dominant strength of the Ps signal and higher resolution of the diffraction resonances, predicted earlier [P.A. Hervieux, A.R. Chakraborty, H.S. Chakraborty, Phys. Rev. A 95, 020701(R) (2017)], in the forward direction. This raises the possibility of experimental deter-mination of the resonances in angle differential measurements. We further analyze our results by comparing the positron scattering versus positron-electron pairing components of the amplitude for better insights
- …
