A strong direct product theorem for quantum query complexity

We show that quantum query complexity satisfies a strong direct product theorem. This means that computing k copies of a function with fewer than k times the quantum queries needed to compute one copy of the function implies that the overall success probability will be exponentially small in k. For a boolean function f, we also show an XOR lemma—computing the parity of k copies of f with fewer than k times the queries needed for one copy implies that the advantage over random guessing will be exponentially small. We do this by showing that the multiplicative adversary method, which inherently satisfies a strong direct product theorem, characterizes bounded-error quantum query complexity. In particular, we show that the multiplicative adversary bound is always at least as large as the additive adversary bound, which is known to characterize bounded-error quantum query complexity.     

Experimental investigation of forecasting methods based on data compression algorithms

We suggest and experimentally investigate a method to construct forecasting algorithms based on data compression methods (or the so-called archivers). By the example of predicting currency exchange rates we show that the precision of thus obtained predictions is relatively high.Translated from Problemy Peredachi Informatsii, No. 1, 2005, pp. 74–78.Original Russian Text Copyright © 2005 by Ryabko, Monarev.Supported in part by the Russian Foundation for Basic Research, project no. 03-01-00495, and INTAS, Grant 00-738.     

New related-key rectangle attacks on reduced AES-192 and AES-256

In this paper, we examine the security of reduced AES-192 and AES-256 against related-key rectangle attacks by exploiting the weakness in the AES key schedule. We find the following two new attacks: 9-round reduced AES-192 with 4 related keys, and 10-round reduced AES-256 with 4 related keys. Our results show that related-key rectangle attack with 4 related keys on 9-round reduced AES-192 requires a data complexity of about 2¹⁰¹ chosen plaintexts and a time complexity of about 2^174.8 encryptions, and moreover, related-key rectangle attack with 4 related keys on 10-round reduced AES-256 requires a data complexity of about 2^97.5 chosen plaintexts and a time complexity of about 2²⁵⁴ encryptions. These attacks are the first known attacks on 9-round reduced AES-192 and 10-round reduced AES-256 with only 4 related keys. Furthermore, we give an improvement of the 10-round reduced AES-192 attack presented at FSE2007, which reduces both the data complexity and the time complexity. Supported by the National Natural Science Foundation of China (Grant No. 60673072), and the National Basic Research Program of China (Grant No. 2007CB311201)     

An NC algorithm for recognizing tree adjoining languages

A parallel algorithm is presented for recognizing the class of languages generated by tree adjoining grammars, a tree rewriting system which has applications in natural language processing. This class of languages is known to properly include all context-free languages; for example, the noncontext-free sets {a ⁿ b ⁿ c ⁿ } and {ww} are in this class. It is shown that the recognition problem for tree adjoining languages can be solved by a concurrent read, concurrent write parallel random-access machine (CRCW PRAM) inO(logn) time using polynomially many processors. Thus, the class of tree adjoining languages is inAC ¹ and hence inNC. This extends a previous result for context-free languages.This research was supported in part by NSF Grants IRI 92-96249, MCS 82-19116-CER, MCS 82-07294, DCR 84-10413, MCS 83-05221, ARO Grant DAA29-84-9-0027, DARPA Grant N00014-85-K-0018, and by the New Jersey Institute of Technology under Grant Nos. 421690 and 211665.     

Communication complexity of matrix computation over finite fields

We investigate the communication complexity of singularity testing in a finite field, where the problem is to determine whether a given square matrixM is singular. We show that, forn×n matrices whose entries are elements of a finite field of sizep, the communication complexity of this problem is (n ² logp). Our results imply tight bounds for several other problems likedetermining the rank andcomputing the determinant.This research was supported in part by NSF Grant CCR-8805978 and AFOSR Grant 87-0-400.     

Absolute results concerning one-way functions and their applications

A new approach to one-way functions is considered. A one-way function is defined to be a function which is easy to compute but hard to invert in the sense that its inverse is not inDTIME(n ^k ) for fixed largek. While this is weaker than the usual definition of one-way functions it requires no complexity-theoretic assumptions. Some of these functions are proved to exist, while the existence of other, stronger functions is shown to bear upon open problems in complexity theory. An application to public-key cryptosystems is given.This work was supported in part by NSA Grant MDA904-87-H-2003 and by NSF Grant MIP-8608137.     

一种基于同态公钥加密的遥感影像数字指纹方案

针对非对称指纹计算复杂性高以及带宽效率低的问题,提出了一种基于同态公钥加密的遥感影像非对称指纹方案。在该方案中,内容提供商通过DCT扩频置乱方法加密遥感影像,运用Bresson同态公钥加密来实现解密密钥的非对称分发,通过客户端解密含指纹的遥感影像拷贝,使不同的解密密钥能够生成不同的含指纹拷贝。方案中公钥加密算法并未直接加密遥感影像,由此降低了计算复杂性并提高了加密效率;同时因为内容提供商只需为多个消费者生成相同的指纹拷贝,通过多播传输将其分发给不同的消费者,因此降低了带宽需求。实验表明：在用户数量较大的情况下,该方案可以有效提高带宽效率及加密效率,能够显著降低数据服务器的计算负载,减少用户等待时间。     

Program complexity using Hierarchical Abstract Computers

A model of program complexity is introduced which combines structural control flow measures with data flow measures. This complexity measure is based upon the prime program decomposition of a program written for a Hierarchical Abstract Computer. It is shown that this measure is consistent with the ideas of information hiding and data abstraction. Because this measure is sensitive to the linear form of a program, it can be used to measure different concrete representations of the same algorithm, as in a structured and an unstructured version of the same program. Application of the measure as a model of system complexity is given for “upstream” processes (e.g. specification and design phases) where there is no source program to measure by other techniques.     

The Complexity of Deciding if a Boolean Function Can Be Computed by Circuits over a Restricted Basis

We study the complexity of the following algorithmic problem: Given a Boolean function f and a finite set of Boolean functions B, decide if there is a circuit with basis B that computes f. We show that if both f and all functions in B are given by their truth-table, the problem is in quasipolynomial-size AC⁰, and thus cannot be hard for AC⁰(2) or any superclass like NC¹, L, or NL. This answers an open question by Bergman and Slutzki (SIAM J. Comput., 2000). Furthermore we show that, if the input functions are not given by their truth-table but in a succinct way, i.e., by circuits (over any complete basis), the above problem becomes complete for the class coNP. Supported in part by DFG Grant Vo 630/5-2 and EPSRC Grant 531174.     

Framework for modeling and analysis of distributed problem-solving systems

Petri nets have the basic concepts necessary to model distributed systems with asynchronous processes. Petri nets are not directly applicable to certain kinds of systems like distributed intelligent systems (DISs). These are complex systems where multiple intelligent agents cooperate through communication to achieve the solution to a problem. The paper identifies the limitations of ordinary Petri nets for modeling DISs and proposes extensions. The extended Petri net incorporates colored tokens, inhibition arcs, non-primitive places and transitions, multiple copies of tokens and cumulative places. It is called a distributed problem-solving Petri net. The definitions and analysis techniques are given and illustrated by means of an example.     

Redundancy filtering and fusion verification for video copy detection

Multimedia Systems - Recently, the frame fusion based video copy detection scheme provides a possibility to detect copies in a continuous query video stream. However, its computational complexity...     

Detection of exact and similar partial copies for copyright protection of manga

Manga, a kind of Japanese comic book, is an important genre in the realm of image publications requiring copyright protection. To copy manga, illegal users generally focus on certain interesting parts from which to make partial copies to apply in their own drawings. With respect to their sources, copying of manga can be divided into two types: (1) exact copies, which duplicate specific contents of manga, such as scanned manga publications (printed copies) and traced outlines of manga (hand-drawn copies), and (2) similar partial copies, which infringe the copyright of manga characters based on their features. In this paper, we propose applying content-based image retrieval methods to detect both exact and similar copies based on two kinds of regions of interest (ROIs): generic ROIs and face ROIs. The method is able not only to locate the partial copies from images with complex backgrounds, but also to report the corresponding copied parts of copyrighted manga pages for exact copy detection and copied manga characters for similar copy detection. The experimental results prove high performance of the proposed method for detecting printed partial copies. In addition, 85 % of hand-drawn and 77 % of similar partial copies were detected with relatively high precision using a database containing more than $10{,}000$ manga pages.     

Elimination of parallel copies using code motion on data dependence graphs

Register allocation regained much interest in recent years due to the development of decoupled strategies that split the problem into separate phases: spilling, register assignment, and copy elimination.Traditional approaches to copy elimination during register allocation are based on interference graphs and register coalescing. Variables are represented as nodes in a graph, which are coalesced, if they can be assigned the same register. However, decoupled approaches strive to avoid interference graphs and thus often resort to local recoloring.A common assumption of existing coalescing and recoloring approaches is that the original ordering of the instructions in the program is not changed. This work presents an extension of a local recoloring technique called Parallel Copy Motion. We perform code motion on data dependence graphs in order to eliminate useless copies and reorder instructions, while at the same time a valid register assignment is preserved. Our results show that even after traditional register allocation with coalescing our technique is able to eliminate an additional 3% (up to 9%) of the remaining copies and reduce the weighted costs of register copies by up to 25% for the SPECINT 2000 benchmarks. In comparison to Parallel Copy Motion, our technique removes 11% (up to 20%) more copies and up to 39% more of the copy costs.     

The equivalence of Horn and network complexity for Boolean functions

Summary We propose in this paper a logical complexity measure — Horn complexity — for Boolean functions which measures the minimal length of quasi-Horn definitions of such functions by propositional formulae. The interest for this complexity measure comes on the one hand from the observation that the satisfiability problem for Horn formulae is in P, on the other hand from a strong connection to Cook's problem. We show the proposed Horn complexity to be polynomially equivalent to network complexity and therefore to Turing complexity for Boolean functions.A preliminary version of this work has appeared in the Proceedings of the 5^th Scandinavian Logic Symposium, edited by B. Mayoh and F. Jensen, Aalborg University Press, Aalborg 1979     

Effective utilization of copies in a transparent distributed environment

In a distributed relational database system, the processing of a query involves data transmission among different sites via a computer network. In a distributed database multiple copies of each relation can be allocated to different, physically distributed sites. In this paper we discuss the query preoptimization problem for join-queries. In general, there is a large number of possibilities to use the copies of the data item in a distributed relational database when evaluating a join-query. We consider the problem of a copy preselection for each relation in a join sequence of a join-query. We show how to express the preselection problem for a given query and data allocation to the network in terms of an integer linear programming problem, namely, a minimum cover problem. It can be treated as a heuristic for the first phase of a join-query optimization, and as such as an input to the final stage of optimization, the execution strategy generation for a join-query. In this paper we assumed that a distributed system provides fully transparent data management, i.e., data allocation to the network and data replication which is revealed to a user. We illustrate the proposed mathematical programming problem through a nontrivial example. Recommended by: R. Elamsri     

Learning to extract and summarize hot item features from multiple auction web sites

It is difficult to digest the poorly organized and vast amount of information contained in auction Web sites which are fast changing and highly dynamic. We develop a unified framework which can automatically extract product features and summarize hot item features from multiple auction sites. To deal with the irregularity in the layout format of Web pages and harness the uncertainty involved, we formulate the tasks of product feature extraction and hot item feature summarization as a single graph labeling problem using conditional random fields. One characteristic of this graphical model is that it can model the inter-dependence between neighbouring tokens in a Web page, tokens in different Web pages, as well as various information such as hot item features across different auction sites. We have conducted extensive experiments on several real-world auction Web sites to demonstrate the effectiveness of our framework. The work described in this paper is substantially supported by grants from the Research Grant Council of the Hong Kong Special Administrative Region, China (Project Nos: CUHK 4179/03E and CUHK4193/04E) and the Direct Grant of the Faculty of Engineering, CUHK (Project Codes: 2050363 and 2050391). This work is also affiliated with the Microsoft-CUHK Joint Laboratory for Human-centric Computing and Interface Technologies.     

An improved technique for output-sensitive hidden surface removal

We derive a new output-sensitive algorithm for hidden surface removal in a collection ofn triangles, viewed from a pointz such that they can be ordered in an acyclic fashion according to their nearness toz. Ifk is the combinatorial complexity of the outputvisibility map, then we obtain a sophisticated randomized algorithm that runs in (randomized) timeO(n^4/3 log^2.89 n +k ^3/5 n ^{4/5 +} for any > 0. The method is based on a new technique for tracing the visible contours using ray shooting.Work by the first author was partially supported by the ESPRIT II Basic Research Actions Program of the EC, under Contract No. 3075 (project ALCOM). Work by the second author has been supported by Office of Naval Research Grant N00014-87-K-0129, by National Science Foundation Grant CCR-89-01484, and by grants from the U.S.-Israeli Binational Science Foundation, the NCRD-the Israeli National Council for Research and Development-and the Fund for Basic Research in Electronics, Computers, and Communication administered by the Israeli Academy of Sciences. A preliminary version of this paper appeared as part of the conference proceedings paper [17].     

Selecting distances in the plane

We present a randomized algorithm for computing the kth smallest distance in a set ofn points in the plane, based on the parametric search technique of Megiddo [Mel]. The expected running time of our algorithm is O(n^4/3 log^8/3 n). The algorithm can also be made deterministic, using a more complicated technique, with only a slight increase in its running time. A much simpler deterministic version of our procedure runs in time O(n^3/2 log^5/2 n). All versions improve the previously best-known upper bound ofO(@#@ n^9/5 log^4/5 n) by Chazelle [Ch]. A simpleO(n logn)-time algorithm for computing an approximation of the median distance is also presented.Part of this work was done while the first two authors were visting DIMACS, Rutgers University, New Brunswick, NJ. Work by the first three authors has been partly supported by Office of Naval Research Grant N00014-87-K-0129, by National Science Foundation Grant DCR-83-20085, and by DIMACS (Center for Discrete Mathematics and Theoretical Computer Science), a National Science Foundation Science and Technology Center-NSF-STC88-09648. Work by the second author has also been supported by National Security Agency Grant MDA 904-89-H-2030. Work by the third author has also been supported by National Science Foundation Grant CCR-89-01484, and by grants from the U.S.-Israeli Binational Science Foundation, and the Fund for Basic Research administered by the Israeli Academy of Sciences.     

A Repeated-Update Problem in the DeltaBlue Algorithm

We observe a repeated-update problem in the process of updating walkabout strengths of the DeltaBlue algorithm, which is known as a fast constraint solving method based on local propagation. According to the basic references on the DeltaBlue algorithm, the time complexity of the planning phase is described as O(MN) for a constraint problem such that the number of constraints is N and the maximum number of methods a constraint has is M . We, however, point out that the time complexity is not O(MN) using a very simple example. In this example, the time complexity is exponential order for N . Then we present a corrected DeltaBlue algorithm whose time complexity is O(EN ²) for a constraint problem such that the number of constraints is N and the maximum number of variables a constraint has is E . Finally we measure the performance of the corrected DeltaBlue algorithm using two benchmarks.     

An efficient retrieval selection algorithm for video servers with random duplicated assignment storage technique

Random Duplicated Assignment (RDA) is an approach in which video data is stored by assigning a number of copies of each data block to different, randomly chosen disks. It has been shown that this approach results in smaller response times and lower disk and RAM costs compared to the well-known disk stripping techniques. Based on this storage approach, one has to determine, for each given batch of data blocks, from which disk each of the data blocks is to be retrieved. This is to be done in such a way that the maximum load of the disks is minimized. The problem is called the Retrieval Selection Problem (RSP). In this paper, we propose a new efficient algorithm for RSP. This algorithm is based on the breadth-first search approach and is able to guarantee optimal solutions for RSP in O(n²+mn), where m and n correspond to the number of data blocks and the number of disks, respectively. We will show that our proposed algorithm has a lower time complexity than an existing algorithm, called the MFS algorithm.