On the Communication Complexity of Secret Key Generation in the Multiterminal Source Model

Communication complexity refers to the minimum rate of public communication required for generating a maximal-rate secret key (SK) in the multiterminal source model of Csiszar and Narayan. Tyagi recently characterized this communication complexity for a two-terminal system. We extend the ideas in Tyagi's work to derive a lower bound on communication complexity in the general multiterminal setting. In the important special case of the complete graph pairwise independent network (PIN) model, our bound allows us to determine the exact linear communication complexity, i.e., the communication complexity when the communication and SK are restricted to be linear functions of the randomness available at the terminals.

Efficient QR Decomposition Using Low Complexity Column-wise Givens Rotation (CGR)

QR decomposition (QRD) is a widely used Numerical Linear Algebra (NLA) kernel with applications ranging from SONAR beamforming to wireless MIMO receivers. In this paper, we propose a novel Givens Rotation (GR) based QRD (GR QRD) where we reduce the computational complexity of GR and exploit higher degree of parallelism. This low complexity Column-wise GR (CGR) can annihilate multiple elements of a column of a matrix simultaneously. The algorithm is first realized on a Two-Dimensional (2 D) systolic array and then implemented on REDEFINE which is a Coarse Grained run-time Reconfigurable Architecture (CGRA). We benchmark the proposed implementation against state-of-the-art implementations to report better throughput, convergence and scalability.

Low Complexity Power and Scheduling Policies for Wireless Networks to Provide Quality of Service

We consider optimal power allocation policies for a single server, multiuser system. The power is consumed in transmission of data only. The transmission channel may experience multipath fading. We obtain very efficient, low computational complexity algorithms which minimize power and ensure stability of the data queues. We also obtain policies when the users may have mean delay constraints. If the power required is a linear function of rate then we exploit linearity and obtain linear programs with low complexity.

On the Parameterized Complexity of Finding Separators with Non-Hereditary Properties

We study the problem of finding small s-t separators that induce graphs having certain properties. It is known that finding a minimum clique s-t separator is polynomial-time solvable (Tarjan in Discrete Math. 55:221-232, 1985), while for example the problems of finding a minimum s-t separator that induces a connected graph or forms an independent set are fixed-parameter tractable when parameterized by the size of the separator (Marx et al. in ACM Trans. Algorithms 9(4): 30, 2013). Motivated by these results, we study properties that generalize cliques, independent sets, and connected graphs, and determine the complexity of finding separators satisfying these properties. We investigate these problems also on bounded-degree graphs. Our results are as follows: Finding a minimum c-connected s-t separator is FPT for c=2 and W1]-hard for any ca parts per thousand yen3. Finding a minimum s-t separator with diameter at most d is W1]-hard for any da parts per thousand yen2. Finding a minimum r-regular s-t separator is W1]-hard for any ra parts per thousand yen1. For any decidable graph property, finding a minimum s-t separator with this property is FPT parameterized jointly by the size of the separator and the maximum degree. Finding a connected s-t separator of minimum size does not have a polynomial kernel, even when restricted to graphs of maximum degree at most 3, unless .

Primates, Provisioning and Plants: Impacts of Human Cultural Behaviours on Primate Ecological Functions

Human provisioning of wildlife with food is a widespread global practice that occurs in multiple socio-cultural circumstances. Provisioning may indirectly alter ecosystem functioning through changes in the eco-ethology of animals, but few studies have quantified this aspect. Provisioning of primates by humans is known to impact their activity budgets, diets and ranging patterns. Primates are also keystone species in tropical forests through their role as seed dispersers; yet there is no information on how provisioning might affect primate ecological functions. The rhesus macaque is a major human-commensal species but is also an important seed disperser in the wild. In this study, we investigated the potential impacts of provisioning on the role of rhesus macaques as seed dispersers in the Buxa Tiger Reserve, India. We studied a troop of macaques which were provisioned for a part of the year and were dependent on natural resources for the rest. We observed feeding behaviour, seed handling techniques and ranging patterns of the macaques and monitored availability of wild fruits. Irrespective of fruit availability, frugivory and seed dispersal activities decreased when the macaques were provisioned. Provisioned macaques also had shortened daily ranges implying shorter dispersal distances. Finally, during provisioning periods, seeds were deposited on tarmac roads that were unconducive for germination. Provisioning promotes human-primate conflict, as commensal primates are often involved in aggressive encounters with humans over resources, leading to negative consequences for both parties involved. Preventing or curbing provisioning is not an easy task as feeding wild animals is a socio-cultural tradition across much of South and South-East Asia, including India. We recommend the initiation of literacy programmes that educate lay citizens about the ill-effects of provisioning and strongly caution them against the practice.

Efficient Low Complexity Power Allocation Policies for Wireless Communication Systems Guaranteeing QoS

We consider near-optimal policies for a single user transmitting on a wireless channel which minimize average queue length under average power constraint. The power is consumed in transmission of data only. We consider the case when the power used in transmission is a linear function of the data transmitted. The transmission channel may experience multipath fading. Later, we also extend these results to the multiuser case. We show that our policies can be used in a system with energy harvesting sources at the transmitter. Next we consider data users which require minimum rate guarantees. Finally we consider the system which has both data and real time users. Our policies have low computational complexity, closed form expression for mean delays and require only the mean arrival rate with no queue length information.

Kernelization complexity of possible winner and coalitional manipulation problems in voting

In the POSSIBLE WINNER problem in computational social choice theory, we are given a set of partial preferences and the question is whether a distinguished candidate could be made winner by extending the partial preferences to linear preferences. Previous work has provided, for many common voting rules, fixed parameter tractable algorithms for the POSSIBLE WINNER problem, with number of candidates as the parameter. However, the corresponding kernelization question is still open and in fact, has been mentioned as a key research challenge 10]. In this paper, we settle this open question for many common voting rules. We show that the POSSIBLE WINNER problem for maximin, Copeland, Bucklin, ranked pairs, and a class of scoring rules that includes the Borda voting rule does not admit a polynomial kernel with the number of candidates as the parameter. We show however that the COALITIONAL MANIPULATION problem which is an important special case of the POSSIBLE WINNER problem does admit a polynomial kernel for maximin, Copeland, ranked pairs, and a class of scoring rules that includes the Borda voting rule, when the number of manipulators is polynomial in the number of candidates. A significant conclusion of our work is that the POSSIBLE WINNER problem is harder than the COALITIONAL MANIPULATION problem since the COALITIONAL MANIPULATION problem admits a polynomial kernel whereas the POSSIBLE WINNER problem does not admit a polynomial kernel. (C) 2015 Elsevier B.V. All rights reserved.

Tutela del patrimonio cultural : marco jurídico estatal

Más de mil "bienes" se habían incorporado hasta el mes de octubre del año 2013 al Registro que lleva la "Comisión Nacional de Museos y de Monumentos y Lugares Históricos", organismo estatal creado en 1940 y que tiene como misión –en sustancia– preservar, defender y acrecentar el patrimonio histórico y artístico de la Nación Argentina. La riqueza y variedad del elenco, que se amplía año a año, son datos que informan acerca del magnífico patrimonio cultural que ostenta el país. Algo más de una quinta parte del Registro, cuyo catálogo se agrupa en diferentes "tipologías", atañe a bienes de naturaleza "religiosa", en altísimo porcentaje concernientes a la Iglesia Católica. Sólo en orden a exhibir la diversidad del repertorio, que atraviesa todo el territorio de la Nación, cabe señalar que fueron declarados como "Monumento Histórico" la Catedral de la ciudad de Salta (Provincia de Salta), el Santuario de Nuestro Señor de los Milagros de Mailín (Provincia de Santiago del Estero), el Monumento al Cristo Redentor de los Andes (Provincia de Mendoza), el Cementerio de la Misión Salesiana (Provincia de Tierra del Fuego) y las Capillas de los Cementerios Británico y Alemán (Ciudad de Buenos Aires)...

Polibio, el mundo helenístico y la problemática cultural : algunas líneas de reflexión en los últimos veinte años

Resumen: Nuestro conocimiento de algunos aspectos de las Historias de Polibio se ha incrementado significativamente durante las dos últimas décadas. En ese sentido, ha habido ciertos desarrollos importantes con respecto a aspectos culturales de la obra, cuyo alcance ha ido permitiendo repensar durante estos años algunos presupuestos clásicos sobre la relación entre Polibio, Roma y el mundo helenístico. Proponemos aquí ofrecer un rápido análisis de las tres principales líneas de estudio propuestas por los estudiosos, cuyo alcance es considerado, en efecto, como un total reubicación del historiador aqueo al interior del universo cultural del mundo helenístico.