Low complexity quantum private queries protocol

Private information retrieval(PIR) is an important privacy protection issue of secure multi-party computation, but the PIR protocols based on classical cryptography are vulnerable because of new technologies,such as quantum computing and cloud computing. The quantum private queries(QPQ) protocols available, however, has a high complexity and is inefficient in the face of large database. This paper, based on the QKD technology which is mature now, proposes a novel QPQ protocol utilizing the key dilution and auxiliary parameter. Only N quits are required to be sent in the quantum channel to generate the raw key, then the straight k bits in the raw key are added bitwise to dilute the raw key, and a final key is consequently obtained to encrypt the database. By flexible adjusting of auxiliary parameters θ and k, privacy is secured and the query success ratio is improved. Feasibility and performance analyses indicate that the protocol has a high success ratio in first-trial query and is easy to implement, and that the communication complexity of O(N) is achieved.     

Optimal shift partitioning of pharmacies

The pharmacy service requires that some pharmacies are always available and shifts have to be organized: a shift corresponds to a subset of pharmacies that must be open 24 hours a day on a particular week. Under the requirement that each pharmacy belongs to exactly one shift and the assumption that users minimize the distance to the closest open pharmacy during each shift, we want to determine a partition of the pharmacies into a given number of shifts, such that the total distance covered by users is minimized. It may be also required that shift cardinalities are balanced. We discuss different versions and the related computational complexity, showing that the problem is NP-hard in general. A set packing formulation is presented and solved by branch-and-price, together with a fast solution technique based on a tabu search. They have been applied to real and random instances showing that (i) the set packing formulation is very tight and often exhibits no integrality gap; (ii) the branch-and-price solves problems of practical relevance to optimality in a reasonable amount of time (order of minutes); (iii) the tabu search finds optimal or near-optimal solutions in order of seconds.     

一种实用的多数据库量子信息检索协议

针对目前量子私有信息检索不能适用与云存储的多数据库问题,基于现在成熟的量子密钥分发方法,提出了一种适合在多数据库环境下,实用的量子私有信息检索协议。对于不同大小的数据库,协议可通过调节参数θ和k,在保证数据库安全及用户隐私的情况下,完成信息的检索。性能分析结果表明,协议的通信复杂度低,检索成功率高、易于实施。     

Creating the brain and interacting with the brain: an integrated approach to understanding the brain

In the past two decades, brain science and robotics have made gigantic advances in their own fields, and their interactions have generated several interdisciplinary research fields. First, in the ‘understanding the brain by creating the brain’ approach, computational neuroscience models have been applied to many robotics problems. Second, such brain-motivated fields as cognitive robotics and developmental robotics have emerged as interdisciplinary areas among robotics, neuroscience and cognitive science with special emphasis on humanoid robots. Third, in brain–machine interface research, a brain and a robot are mutually connected within a closed loop. In this paper, we review the theoretical backgrounds of these three interdisciplinary fields and their recent progress. Then, we introduce recent efforts to reintegrate these research fields into a coherent perspective and propose a new direction that integrates brain science and robotics where the decoding of information from the brain, robot control based on the decoded information and multimodal feedback to the brain from the robot are carried out in real time and in a closed loop.     

Age of acquisition: Its neural and computational mechanisms.

The acquisition of new skills over a life span is a remarkable human ability. This ability, however, is constrained by age of acquisition (AoA); that is, the age at which learning occurs significantly affects the outcome. This is most clearly reflected in domains such as language, music, and athletics. This article provides a perspective on the neural and computational mechanisms underlying AoA in language acquisition. The authors show how AoA modulates both monolingual lexical processing and bilingual language acquisition. They consider the conditions under which syntactic processing and semantic processing may be differentially sensitive to AoA effects in second-language acquisition. The authors conclude that AoA effects are pervasive and that the neural and computational mechanisms underlying learning and sensorimotor integration provide a general account of these effects. (PsycINFO Database Record (c) 2010 APA, all rights reserved)     

On the complexity of simulating space-bounded quantum computations

This paper studies the space-complexity of predicting the long-term behavior of a class of stochastic processes based on evolutions and measurements of quantum mechanical systems. These processes generalize a wide range of both quantum and classical space-bounded computations, including unbounded error computations given by machines having algebraic number transition amplitudes or probabilities. It is proved that any space s quantum stochastic process from this class can be simulated probabilistically with unbounded error in space O(s), and therefore deterministically in space O(s²).     

Integrating psychology and politics.

Comments on the article "A house divided? The psychology of red and blue America" by D. C. Seyle and M. L. Newman (see record 2006-11202-001). Seyle and Newman concluded that the red and blue metaphor is inaccurate and proposed a purple America strategy to better convey that the majority of people do not align themselves with political extremes. There is interdisciplinary agreement on this. Although not cited by Seyle and Newman, the findings by Professor Fiorina of Stanford University were reported by the APA Monitor on Psychology in its coverage of the 2005 APA State Leadership Conference (Murray Law, 2005). In contrast to their social psychological analysis, Seyle and Newman were incorrect in concluding that "[a]s psychologists, we are not in a position to change either the elements of the American political system that may spur this conflict or even the decisions made by pundits, politicians, and reporters about the terms they choose to use in political discussion" (p. 579). (PsycINFO Database Record (c) 2010 APA, all rights reserved)     

The complexity of economic equilibria for house allocation markets

We prove NP-completeness of deciding the existence of an economic equilibrium in so-called house allocation markets. House allocation markets are markets with indivisible goods in which every agent holds exactly one copy of some good.     

Local Exact Particle Tracing on Unstructured Grids

For analyzing and interpreting results of flow simulations, particle tracing is a well established visualization method. In addition, it is a preliminary step for more advanced techniques such as line integral convolution. For interactive exploration of large data sets, a very efficient and reliable particle tracing method is needed. For wind channel experiments or flight simulations, large unstructured computational grids have become common practice. Traditional approachs, based on numerical integration methods of ordinary differential equations however fail to deliver sufficiently accurate path calculation at the speed required for interactive use. In this paper we extend the local exact approach of Nielson and Jung in such a way that it can be used for interactive particle tracing in large data sets of steady flow simulation experiments. This will be achieved by sophisticated preprocessing using additional memory. For further visual enhancement of the streamline we construct an implicitly defined smooth Bézier curve that is used for ray tracing. This allows us to visualize additional scalar values of the simulation as attributes to the trajectory and enables the display of high‐quality smooth curves without creating any visualization geometry and providing a good impression of the spatial situation at the same time. ACM CSS: I.3.3 Computer Graphics—Line and curve generation; I .3.7 Computer Graphics—Raytracing; G.1.2 Numerical Analysis—Spline and piecewise polynomial approximation     

Modeling language acquisition in atypical phenotypes.

An increasing number of connectionist models have been proposed to explain behavioral deficits in developmental disorders. These simulations motivate serious consideration of the theoretical implications of the claim that a developmental disorder fits within the parameter space of a particular computational model of normal development. The authors examine these issues in depth with respect to a series of new simulations investigating past-tense formation in Williams syndrome. This syndrome and the past-tense domain are highly relevant because both have been used to make strong theoretical claims about the processes underlying normal language acquisition. The authors conclude that computational models have great potential to advance psychologists' understanding of developmental deficits because they focus on the developmental process itself as a pivotal causal factor in producing atypical phenotypic outcomes. (PsycINFO Database Record (c) 2010 APA, all rights reserved)