Accurate prediction of television (TV) audience ratings is a crucial technology for advertisers and broadcast-ers, which influences advertising costs and indicates program popularity. As for Japanese TV dramas, previous studies have examined factors available prior to broadcast, such as cast com-position, metadata variables (e.g., scheduled time slot, broadcasting station, episode duration), and indicators of actor popularity. However, such studies have been limited in their evaluation of contextual information related to these factors and have not considered additional modalities such as text data. Here, we propose the use of knowledge-based embeddings derived from Japanese Wikipedia to improve audience ratings prediction. The proposed bag-of-entities method is applied to represent dramas in terms of cast, production team, and plot synopsis elements, and is evaluated against conventional metadata features. In an ablation study, supervised forecasting models using Support Vector Machine (SVM) are trained on combinations of the feature groups. These are devised and tested on viewership data collected from the Audience Rating TV (ARTV) database for 574 Japanese TV dramas aired between 2003 and 2021. Our experimental results indicate that a SVM model conditioned on the full feature set outperforms baseline methods, achieving a 77.4 % F1-score. After stratifying predictions based on time slot popularity, the approach is found to be effective for predicting audience ratings in challenging, high-popularity time slots, with improvements in recognition rate up to 19.1 %.

d-dimensional (for d > 1) efficient range-summability (dD-ERS) of random variables (RVs) is a fundamental algorithmic problem that has applications to two important families of database problems, namely, fast approximate wavelet tracking (FAWT) on data streams and approximately answering range-sum queries over a data cube. Whether there are efficient solutions to the dD-ERS problem, or to the latter database problem, have been two long-standing open problems. Both are solved in this work. Specifically, we propose a novel solution framework to dD-ERS on RVs that have Gaussian or Poisson distribution. Our dD-ERS solutions are the first ones that have polylogarithmic time complexities. Furthermore, we develop a novel k-wise independence theory that allows our dD-ERS solutions to have both high computational efficiencies and strong provable independence guarantees. Finally, we show that under a sufficient and likely necessary condition, certain existing solutions for 1D-ERS can be generalized to higher dimensions.

Efficient range-summability (ERS) of a long list of random variables is a fundamental algorithmic problem that has applications to three important database applications, namely, data stream processing, space-efficient histogram maintenance (SEHM), and approximate nearest neighbor searches (ANNS). In this work, we propose a novel dyadic simulation framework and develop three novel ERS solutions, namely Gaussian-dyadic simulation tree (DST), Cauchy-DST and Random Walk-DST, using it. We also propose novel rejection sampling techniques to make these solutions computationally efficient. Furthermore, we develop a novel k-wise independence theory that allows our ERS solutions to have both high computational efficiencies and strong provable independence guarantees.

Personalized medicine is becoming of increasing importance in the study of psoriasis and atopic dermatitis (AD). Because current treatments only target symptoms, early intervention and personalized medicine have a pivotal role in improved health outcomes. To explore this potential, this study investigates the use of direct-to-consumer (DTC) genetic data in devising machine learning models that can pinpoint signatures salient to psoriasis and AD. The study simulates high-dimensional datasets derived from the HapMap 3 and 1000 Genomes Project cohorts (561K and 497K loci, respectively, that act as features). The simulation scheme splits subjects into cases and controls, where randomly selected variants associated with the target phenotypes are introduced into the cases. Unsupervised learning (UMAP) and eight supervised learning techniques are applied to each of the simulated datasets. Our findings suggest that the parametric models tested (SVM, LASSO, and RIDGE) exhibit the best predictive power on the simulated datasets while also yielding high retrieval rates for signatures associated with the target phenotypes.

In this work, we formulate and solve a new type of approximate nearest neighbor search (ANNS) problems called ANNS after linear transformation (ALT). In ANNS-ALT, we search for the vector (in a dataset) that, after being linearly transformed by a user-specified query matrix, is closest to a query vector. It is a very general mother problem in the sense that a wide range of baby ANNS problems that have important applications in databases and machine learning can be reduced to and solved as ANNS-ALT, or its dual that we call ANNS-ALTD. We propose a novel and computationally efficient solution, called ONe Index for All Kernels (ONIAK), to ANNS-ALT and all its baby problems when the data dimension d is not too large (say d ≤ 200). In ONIAK, a universal index is built, once and for all, for answering all future ANNS-ALT queries that can have distinct query matrices. We show by experiments that, when d is not too large, ONIAK has better query performance than linear scan on the mother problem (of ANNS-ALT), and has query performances comparable to those of the state-of-the-art solutions on the baby problems. However, the algorithmic technique behind this universal index approach suffers from a so-called dimension blowup problem that can make the indexing time prohibitively long for a large dataset. We propose a novel algorithmic technique, called fast GOE quadratic form (FGoeQF), that completely solves the (prohibitively long indexing time) fallout of the dimension blowup problem. We also propose a Johnson-Lindenstrauss transform (JLT) based ANNS-ALT (and ANNS-ALTD) solution that significantly outperforms any competitor when d is large.

Approximate Nearest Neighbor Search (ANNS) is a fundamental algorithmic problem, with numerous applications in many areas of computer science. Locality-Sensitive Hashing (LSH) is one of the most popular solution approaches for ANNS. A common shortcoming of many LSH schemes is that since they probe only a single bucket in a hash table, they need to use a large number of hash tables to achieve a high query accuracy. For ANNS- L 2 , a multi-probe scheme was proposed to overcome this drawback by strategically probing multiple buckets in a hash table. In this work, we propose MP-RW-LSH, the first and so far only multi-probe LSH solution to ANNS in L 1 distance, and show that it achieves a better tradeoff between scalability and query efficiency than all existing LSH-based solutions. We also explain why a state-of-the-art ANNS -L 1 solution called Cauchy projection LSH (CP-LSH) is fundamentally not suitable for multi-probe extension. Finally, as a use case, we construct, using MP-RW-LSH as the underlying "ANNS- L 1 engine", a new ANNS-E (E for edit distance) solution that beats the state of the art.

Today's measurement instruments are capable of capturing and processing massive amount of waveform data. High sampling rate Analog to Digital Converters (ADCs) and low-cost storages make it relatively easy to collect "big measurement data" at massive scale. More and more measurement instrument users acquire tera-byte-scale waveform data which are essential for hard-to-find failure detection and prediction. However, conventional analysis techniques focus on small fragments of signals and largely lag behind today's test and measurement data assets' processing demands. Most of these techniques are inadequate for coping with the massive data volume and the complexities of the analysis tasks. A previous report by the authors introduced a heterogeneous waveform clustering framework to break the technical barriers. The present paper demonstrates the effectiveness of the proposed framework with real-world application examples at tera-byte data scale. The framework consists of the real-time tagging for pre-sorting incoming data, quick clustering for summarizing data overviews from long-duration recording, and detail clustering for deeper analyses. The tagging process is the critical performance link for satisfying the processing time and hardware constrains. We share theoretical analysis on the degree of freedom involved in the waveform and the tagging results. The data is pre-sorted into tag database with highly efficient retrieval characteristics, allowing the system to provide results quickly and flexibly. Three real-world waveform analysis examples are demonstrated, namely power line voltage, mechanical relay stick error, and Bluetooth device current consumption. Our framework allows efficient and robust exploration of complex signal signatures for detecting extremely rare anomalies. The detected anomaly patterns not only show straightforward engineering usages, but also demonstrate a predictive analysis power of related signal events.

In this paper, we investigate the complexity of a number of computational problems defined on a synchronous boolean finite dynamical system, where update functions are chosen from a template set of exclusive-or and its negation. We first show that the reachability and path-intersection problems are solvable in logarithmic space-uniform AC¹ if the objects execute permutations, while the reachability problem is known to be in P and the path-intersection problem to be in UP in general. We also explore the case where the reachability or intersection are tested on a subset of objects, and show that this hardens complexity of the problems: both problems become NP-complete, and even Π^p₂-complete if we further require universality of the intersection. We next consider the exact cycle length problem, that is, determining whether there exists an initial configuration that yields a cycle in the configuration space having exactly a given length, and show that this problem is NP-complete. Lastly, we consider the t-predecessor and t-Garden of Eden problem, and prove that these are solvable in polynomial time even if the value of t is also given in binary as part of instance, and the two problems are in logarithmic space-uniform NC² if the value of t is given in unary as part of instance.

Set reconciliation is a fundamental algorithmic problem that arises in many networking, system, and database applications. In this problem, two large sets A and B of objects (bitcoins, files, records, etc.) are stored respectively at two different network-connected hosts, which we name Alice and Bob respectively. Alice and Bob communicate with each other to learn A Δ B , the difference between A and B , and as a result the reconciled set A ∪ B. Current set reconciliation schemes are based on either invertible Bloom filters (IBF) or error-correction codes (ECC). The former has a low computational complexity of O(d) , where d is the cardinality of A Δ B , but has a high communication overhead that is several times larger than the theoretical minimum. The latter has a low communication overhead close to the theoretical minimum, but has a much higher computational complexity of O(d 2 ). In this work, we propose Parity Bitmap Sketch (PBS), an ECC-based set reconciliation scheme that gets the better of both worlds: PBS has both a low computational complexity of O(d) just like IBF-based solutions and a low communication overhead of roughly twice the theoretical minimum. A separate contribution of this work is a novel rigorous analytical framework that can be used for the precise calculation of various performance metrics and for the near-optimal parameter tuning of PBS.

Approximate Nearest Neighbor (ANN) search is a fundamental algorithmic problem, with numerous applications in many areas of computer science. In this work, we propose indexable distance estimating codes (iDEC) , a new solution framework to ANN that extends and improves the locality sensitive hashing (LSH) framework in a fundamental and systematic way. Empirically, an iDEC-based solution has a low index space complexity of O ( n ) and can achieve a low average query time complexity of approximately O (log n ). We show that our iDEC-based solutions for ANN in Hamming and edit distances outperform the respective state-of-the-art LSH-based solutions for both in-memory and external-memory processing. We also show that our iDEC-based in-memory ANN-H solution is more scalable than all existing solutions. We also discover deep connections between Error-Estimating Codes (EEC), LSH, and iDEC.

Modern oscilloscopes, digitizers and data loggers generate a large amount of waveform data for long-duration waveform capturing and analysis. The contrast of time scales of long-duration waveform capturing (e.g., hours or days in high sampling rate) and analysis (e.g., signal fragments of several microseconds) produces unique big data challenges. The proposed long-duration waveform clustering algorithms are designed for signal waveform analysis and user interaction for various “big-data” waveform analysis scenarios. To cope with the real-time processing demand and the hardware constraints of the target platforms, the proposed algorithm utilizes multiple layers of data pre-sorting, database query, and waveform similarity-based clustering for versatile speed-precision tradeoffs. We integrated the system as an intuitive big waveform data analytics framework which provides unprecedented performance and productivity to engineers and scientists. Experimental result shows superb speed and data volume capability.

Popular music lyrics are usually brief in length yet sophisticated in narrative content, emotional expression, and structural aesthetics. In this paper, we propose a graph-based analysis and interpretation framework for popular music lyrics using the sematic word embedding representation. This framework explores the temporal and structural information in music lyrics, such as word sequential pattern, lyric format pattern, and predominate song forms, to enhance the understanding of the interaction between the semantic and structural properties of music lyrics. Our proposed analysis and interpretation framework provides extensive tools for representing various properties of music lyrics as graph structural elements and then we implemented feature extraction tools for a comprehensive characterization of the lyric graph using graph analysis or complex network methodologies. The empirical studies based on contrasting music genres are then presented to illustrate the usage of the proposed tools and to demonstrate its modeling and analysis capabilities.

The recent advancement of web-scale digital advertising saw a paradigm shift from the conventional focus of digital advertisement distribution towards integrating digital processes and methodologies and forming a seamless workflow of advertisement design, production, distribution, and effectiveness monitoring. In this work, we implemented a computational framework for the predictive analysis of the content-based features extracted from advertisement video files and various effectiveness metrics to aid the design and production processes of commercial advertisements. Our proposed predictive analysis framework extracts multi-dimensional temporal patterns from the content of advertisement videos using multimedia signal processing and natural language processing tools. The pattern analysis part employs an architecture of cross modality feature learning where data streams from different feature dimensions are employed to train separate neural network models and then these models are fused together to learn a shared representation. Subsequently, a neural network model trained on this joint representation is utilized as a classifier for predicting advertisement effectiveness. Based on the predictive patterns identified between the content features and the effectiveness metrics of advertisements, we have elicited a useful set of auditory, visual and textual patterns that is strongly correlated with the proposed effectiveness metrics while can be readily implemented in the design and production processes of commercial advertisements. We validate our approach using subjective ratings from a dedicated user study, the text sentiment strength of online viewer comments, and a viewer opinion metric of the likes/views ratio of each advertisement from YouTube video-sharing website.

This paper investigates the use of linguistic features extracted from the application essays of students enrolled in a university academic program for their retention pattern prediction. Three sets of linguistic features are generated from text analysis: (1) latent Dirichlet allocation (LDA) based topic modeling with a variety of topic numbers, (2) Linguistic Inquiry and Word Count (LIWC), and (3) part-of-speech (POS) distribution. Various classification experiments are implemented to evaluate the prediction performance of student retention patterns from these three feature sets and their combinations. The results show that the POS distribution features yield the best prediction performance among these three, while neither the LDA features nor ensemble methods improves predictive performance, which is contrary to admission experts' manual analysis methods in the conventional admission processes.

A Boolean Finite Synchronous Dynamical System (BFDS, for short) consists of a finite number of objects that each maintains a boolean state, where after individually receiving state assignments, the objects update their state with respect to object-specific time-independent boolean functions synchronously in discrete time steps. The present paper studies the computational complexity of determining, given a boolean finite synchronous dynamical system, a configuration, which is a boolean vector representing the states of the objects, and a positive integer t, whether there exists another configuration from which the given configuration can be reached in t steps. It was previously shown that this problem, which we call the t-Predecessor Problem, is NP-complete even for t = 1 if the update function of an object is either the conjunction of arbitrary fan-in or the disjunction of arbitrary fan-in. This paper studies the computational complexity of the t-Predecessor Problem for a variety of sets of permissible update functions as well as for polynomially bounded t. It also studies the t-Garden-Of-Eden Problem, a variant of the t-Predecessor Problem that asks whether a configuration has a t-predecessor, which itself has no predecessor. The paper obtains complexity theoretical characterizations of all but one of these problems.

Temporal contour shapes are closely linked to the narrative structure of multimedia content and provide important reference points in content-based multimedia timeline analysis. In this paper, multimedia timeline is extracted from content as time varying video and audio signal features. A temporal contour representation is implemented based on sequential pattern discovery algorithm for modeling the variation contours of multimedia features. The proposed contour representation extracts repetitive temporal patterns from a hierarchy of time resolutions or from synchronized video/audio feature dimensions. The statistically significant contour components, depicting the dominant timeline shapes, are utilized as a structural or analytical representation of the timeline. The modeling performance of this proposed temporal modeling framework is demonstrated through empirical validation and subjective evaluations.

The five articles in this special section focus on data mining techniques and applications in the music industry. Music has been an important application area for data mining and machine learning techniques for many years. Music data mining is an interdisciplinary area that studies computational methods for understanding and delivering music data and is a topic of growing importance with large commercial relevance and substantial potential. The research area of music data mining has gradually evolved during this time period in order to address the challenge of effectively accessing and interacting with these increasing large collections of music and associated data such as styles, artists, lyrics and music reviews. The algorithms and systems developed frequently employ sophisticated and advanced data mining and machine learning techniques in their attempt to better capture the frequently elusive relevant music information.

This paper introduces a novel framework for generating pictorial storylines for given topics from text and image data on the Internet. Unlike traditional text summarization and timeline generation systems, the proposed framework combines text and image analysis and delivers a storyline containing textual, pictorial, and structural information to provide a sketch of the topic evolution. A key idea in the framework is the use of an approximate solution for the dominating set problem. Given a collection of topic-related objects consisting of images and their text descriptions, a weighted multi-view graph is first constructed to capture the contextual and temporal relationships among these objects. Then the objects are selected by solving the minimum-weighted connected dominating set problem defined on this graph. Comprehensive experiments on real-world data sets demonstrate the effectiveness of the proposed framework.

Social tags have been acknowledged as a highly useful resource in retrieving music by moods or topics. However, since social tags are open for labeling, some social tags are inaccurate. In this paper, we present a new framework to identify accurate social tags of songs. In our framework, we first clean and filter music tags. Then we apply an improved hierarchical clustering algorithm to group the tags to build a tag category. Based on the category, we classify music songs using lyrics. In order to extend the semantic information of lyrics, we apply CLOPE to cluster lyrics and use the centroid of the corresponding cluster to represent the lyrics. Based on the Na\"ive Bayes method, the probability of assigning lyrics to particular class is predicted. The classification result is then used to determine whether a social tag is accurate. The experimental results show that the proposed framework is effective and encouraging.

Identifying functional modules from protein-protein interaction networks is an important and challenging task. This paper presents a new approach called PPIBM which is designed to integrate gene expression data analysis and clustering of protein-protein interactions. The proposed approach relies on a Bayesian model which uses as its base protein-protein interactions given as part of input. The proposed method is evaluated with standard measures and its performance is compared with the state-of-the-art network analysis methods. Experimental results on both real-world data and synthetic data demonstrate the effectiveness of the proposed approach.

We proposed a method to classify songs in the Million Song Dataset according to song genre. Since songs have several data types, we trained sub-classifiers by different types of data. These sub-classifiers are combined using both classifier authority and classification confidence for a particular instance. In the experiments, the combined classifier surpasses all of these sub-classifiers and the SVM classifier using concatenated vectors from all data types. Finally, the genre labels for the Million Song Dataset are provided.

With the rapid growth of social media websites, microblogging has become a popular way to spread instant news and events. Due to the dynamic and social nature of microblogs, extracting useful information from microblogs is more challenging than from the traditional news articles. In this paper we study the problem of summarizing the differences from microblogs. Given a collection of microblogs discussing an event/topic, we propose to generate a short summary delivering the differences among these microblogs, such as the different points of view for a news topic and the changes and evolution of an ongoing event.

In music information retrieval (MIR) an important research topic, which has attracted much attention recently, is the utilization of user-assigned tags, artist-related style, and mood labels, which can be extracted from music listening web sites, such as Last.fm (http://www.last.fm/) and All Music Guide (http://www.allmusic.com/). A fundamental research problem in the area is how to understand the relationships among artists/songs and these different pieces of information. Co-clustering is the problem of simultaneously clustering two types of data (e.g., documents and words, and webpages and urls). We can naturally bring this idea to the situation at hand and consider clustering artists and tags together, artists and styles together, or artists and mood labels together. Once such co-clustering has been successfully completed, one can identify co-existing clusters of artists and tags, styles, or mood labels (T/S/M). For simplicity, we use the acronym T/S/M to refer to tag(s), style(s), or mood(s) for the rest of the paper. When dealing with tags it is worth noticing that some tags are more specific versions of others. This naturally suggests that the tags could be organized in hierarchical clusters. Such hierarchical organizations exist for styles and mood labels, so we will consider hierarchical co-clustering of artists and T/S/M. In this paper, we systematically study the application of hierarchical co-clustering (HCC) methods for organizing the music data. There are two standard strategies for hierarchical clustering. One is the divisive strategy, in which we attempt to divide the input data set into smaller groups recursively, and the other is the agglomerative strategy, in which we attempt to combine initially individually separated data points into larger groups by finding the most closely related pair at each iteration. We will compare these two strategies against each other. We apply a previously known divisive hierarchical co-clustering method and a novel agglomerative hierarchical co-clustering. In addition, we demonstrate that these two methods have the capability of incorporating instance-level constraints to achieve better performance. We perform experiments to show that these two hierarchical co-clustering methods can be effectively deployed for organizing the music data and they present reasonable clustering performance comparing with the other clustering methods. A case study is also conducted to show that HCC provides us a new method to quantify the artist similarity.

An important issue in protein-protein interaction network studies is the identification of interaction dynamics. Two factors contribute to the dynamics. One, not all proteins may be expressed in a given cell, and two, competition may exist among multiple proteins for a particular protein domain. Taking into account these two factors, we propose a novel approach to predict protein-protein interaction network dynamics by learning from conflict-sensitive phosphorylation dynamics. We built a training model from conflict-sensitive phosphorylation dynamics [3]. In this model, each node is not an individual protein but a protein-protein pair and is labeled with terms representing conditions in which the interaction should be observed. We mapped the protein pairs in a vector space, built hyper-edges over the interaction nodes, and developed rank-like SVM with Laplacian regularizers for PPI network dynamics prediction. We also employed the standard Fl measure for evaluating the effectiveness of classification results.

Some emerging applications deal with graph data and relie on graph matching and mining. The service-oriented graph matching and mining tool has been required. In this demo we present the web service tool WS-GraphMatching which supports the efficient and visualized matching of polytrees, series-parallel graphs, and arbitrary graphs with bounded feedback vertex set. Its embedded matching algorithms take in account the similarity of vertex-to-vertex and graph structures, allowing path contraction, vertex deletion, and vertex insertions. It provides one-to-one matching queries as well as queries in batch modes including one-to-many matching mode and many-to-many matching mode. It can be used for predicting unknown structured information, comparing and finding conserved patterns, and resolving ambiguous identification of vertices.

In today's Internet applications or sensor networks we often encounter large amounts of data spread over many physically distributed nodes. The sheer volume of the data and bandwidth constraints make it impractical to send all the data to one central node for query processing. Finding distributed icebergs—elements that may have low frequency at individual nodes but high aggregate frequency—is a problem that arises commonly in practice. In this paper we present a novel algorithm with two notable properties. First, its accuracy guarantee and communication cost are independent of the way in which element counts (for both icebergs and non-icebergs) are split amongst the nodes. Second, it works even when each distributed data set is a stream (i.e., one pass data access only). Our algorithm builds upon sketches constructed for the estimation of the second frequency moment (F2) of data streams. The intuition of our idea is that when there are global icebergs in the union of these data streams the F2of the union becomes very large. This quantity can be estimated due to the summable nature of F2sketches. Our key innovation here is to establish tight theoretical guarantees of our algorithm, under certain reasonable assumptions, using an interesting combination of convex ordering theory and large deviation techniques.

It has been well recognized that identifying very large flows (i.e., elephants) in a network traffic stream is important for a variety of network applications ranging from traffic engineering to anomaly detection. However, we found that many of these applications have an increasing need to monitor not only the few largest flows (say top 20), but also all of the medium-sized flows (say top 20,000). Unfortunately, existing techniques for identifying elephant flows at high link speeds are not suitable and cannot be trivially extended for identifying the medium-sized flows. In this work, we propose a hybrid SRAM/DRAM algorithm for monitoring all elephant and medium-sized flows with strong accuracy guarantees. We employ a synopsis data structure (sketch) in SRAM to filter out small flows and preferentially sample medium and large flows to a flow table in DRAM. Our key contribution is to show how to maximize the use of SRAM and DRAM available to us by using a SRAM/DRAM hybrid data structure that can achieve more than an order of magnitude higher SRAM efficiency than previous methods. We design a quantization scheme that allows our algorithm to "read just enough" from the sketch at SRAM speed, without sacrificing much estimation accuracy. We provide analytical guarantees on the accuracy of the estimation and validate these by means of trace-driven evaluation using real- world packet traces..

This paper presents a novel method for mining product reviews, where it mines reviews by identifying product features, expressions of opinions and relations between them. By taking advantage of the fact that most of product features are phrases, a concept of shallow dependency parsing is introduced, which extends traditional dependency parsing to phrase level. This concept is then implemented for extracting relation between product features and expressions of opinions. Experimental evaluations show that the mining task can benefit from shallow dependency parsing.

Music recommendation is receiving increasing attention as the music industry develops venues to deliver music over the Internet. The goal of music recommendation is to present users lists of songs that they are likely to enjoy. Collaborative-filtering and content-based recommendations are two widely used approaches that have been proposed for music recommendation. However, both approaches have their own disadvantages: collaborative-filtering methods need a large collection of user history data and content-based methods lack the ability of understanding the interests and preferences of users. To overcome these limitations, this paper presents a novel dynamic music similarity measurement strategy that utilizes both content features and user access patterns. The seamless integration of them significantly improves the music similarity measurement accuracy and performance. Based on this strategy, recommended songs are obtained by a means of label propagation over a graph representing music similarity. Experimental results on a real data set collected from http://www.newwisdom.net demonstrate the effectiveness of the proposed approach.

Efficient and intelligent music information retrieval is a very important topic of the 21st century. With the ultimate goal of building personal music information retrieval systems, this paper studies the problem of identifying ldquosimilarrdquo artists using features from diverse information sources. In this paper, we first present a clustering algorithm that integrates features from both sources to perform bimodal learning. We then present an approach based on the generalized constraint clustering algorithm by incorporating the instance-level constraints. The algorithms are tested on a data set consisting of 570 songs from 53 albums of 41 artists using artist similarity provided by All Music Guide. Experimental results show that the accuracy of artist similarity identification can be significantly improved.

Entropy has recently gained considerable significance as an important metric for network measurement. Previous research has shown its utility in clustering traffic and detecting traffic anomalies. While measuring the entropy of the traffic observed at a single point has already been studied, an interesting open problem is to measure the entropy of the traffic between every origin-destination pair. In this paper, we propose the first solution to this challenging problem. Our sketch builds upon and extends the Lp sketch of Indyk with significant additional innovations. We present calculations showing that our data streaming algorithm is feasible for high link speeds using commodity CPU/memory at a reasonable cost. Our algorithm is shown to be very accurate in practice via simulations, using traffic traces collected at a tier-1 ISP backbone link.

Efficient and intelligent music information retrieval is a very important topic of the 21st century. With the ultimate goal of building personal music information retrieval systems, this paper studies the problem of identifying "similar" artists using both lyrics and acoustic data. In this paper, we present a clustering algorithm that integrates features from both sources to perform bimodal learning. The algorithm is tested on a data set consisting of 570 songs from 53 albums of 41 artists using artist similarity provided by All Music Guide. Experimental results show that the accuracy of artist similarity classifiers can be significantly improved and that artist similarity can be efficiently identified.

Most application's performance is impacted by the amount of available memory. In a traditional application, which has a fixed working set size, increasing memory has a beneficial effect up until the application's working set is met. In the presence of garbage collection this relationship becomes more complex. While increasing the size of the program's heap reduces the frequency of collections, collecting a heap with memory paged to the backing store is very expensive. We first demonstrate the presence of an optimal heap size for a number of applications running on a machine with a specific configuration. We then introduce a scheme which adaptively finds this good heap size. In this scheme, we track the memory usage and number of page faults at a program's phase boundaries. Using this information, the system selects the soft heap size. By adapting itself dynamically, our scheme is independent of the underlying main memory size, code optimizations, and garbage collection algorithm. We present several experiments on real applications to show the effectiveness of our approach. Our results show that program-level heap control provides up to a factor of 7.8 overall speedup versus using the best possible fixed heap size controlled by the virtual machine on identical garbage collectors.

Finding icebergs – items whose frequency of occurrence is above a certain threshold – is an important problem with a wide range of applications. Most of the existing work focuses on iceberg queries at a single node. However, in many real-life applications, data sets are distributed across a large number of nodes. Two naïve approaches might be considered. In the first, each node ships its entire data set to a central server, and the central server uses single-node algorithms to find icebergs. But it may incur prohibitive communication overhead. In the second, each node submits local icebergs, and the central server combines local icebergs to find global icebergs. But it may fail because in many important applications, globally frequent items may not be frequent at any node. In this work, we propose two novel schemes that provide accurate and efficient solutions to this problem: a sampling-based scheme and a counting-sketch-based scheme. In particular, the latter scheme incurs a communication cost at least an order of magnitude smaller than the naïve scheme of shipping all data, yet is able to achieve very high accuracy. Through rigorous theoretical and experimental analysis we establish the statistical properties of our proposed algorithms, including their accuracy bounds.

In POPL 2002, Petrank and Rawitz showed a universal result— finding optimal data placement is not only NP-hard but also impossible to approximate within a constant factor if P ̸ = NP. Here we study a recently published concept called reference affinity, which characterizes a group of data that are always accessed together in computation. On the theoretical side, we give the complexity for finding reference affinity in program traces, using a novel reduction that converts the notion of distance into satisfiability. We also prove that reference affinity automatically captures the hierarchical locality in divide-and-conquer computations including matrix solvers and N-body simulation. The proof establishes formal links between computation patterns in time and locality relations in space. On the practical side, we show that efficient heuristics exist. In particular, we present a sampling method and show that it is more effective than the previously published technique, especially for data that are often but not always accessed together. We show the effect on generated and real traces. These theoretical and empirical results demonstrate that effective data placement is still attainable in general-purpose programs because common (albeit not all) locality patterns can be precisely modeled and efficiently analyzed.

Efficient and intelligent music information retrieval is a very important topic of the 21st century. With the ultimate goal of building personal music information retrieval systems, this paper studies the problem of intelligent music information retrieval. Huron points out that since the preeminent functions of music are social and psychological, the most useful characterization would be based on four types of information: genre, emotion, style,and similarity. This paper introduces Daubechies Wavelet Coefficient Histograms (DWCH)for music feature extraction for music information retrieval. The histograms are computed from the coefficients of the db/sub 8/ Daubechies wavelet filter applied to 3 s of music. A comparative study of sound features and classification algorithms on a dataset compiled by Tzanetakis shows that combining DWCH with timbral features (MFCC and FFT), with the use of multiclass extensions of support vector machine,achieves approximately 80% of accuracy, which is a significant improvement over the previously known result on this dataset. On another dataset the combination achieves 75% of accuracy. The paper also studies the issue of detecting emotion in music. Rating of two subjects in the three bipolar adjective pairs are used. The accuracy of around 70% was achieved in predicting emotional labeling in these adjective pairs. The paper also studies the problem of identifying groups of artists based on their lyrics and sound using a semi-supervised classification algorithm. Identification of artist groups based on the Similar Artist lists at All Music Guide is attempted. The semi-supervised learning algorithm resulted in nontrivial increases in the accuracy to more than 70%. Finally, the paper conducts a proof-of-concept experiment on similarity search using the feature set.

Automatic music genre classification is a fundamental component of music information retrieval systems and has been gaining importance and enjoying a growing amount of attention with the emergence of digital music on the Internet. Although considerable research has been conducted in automatic music genre classification, little has been done on hierarchical classification with taxonomies. The underlying hierarchical taxonomy identifies the relationships of dependence between different genres and provides valuable sources of information for genre classification. This paper investigates the use of taxonomy for music genre classification. Our empirical experiments on two datasets show that using taxonomy improves the classification performance. We also propose an approach for automatically generating genre taxonomies based on the confusion matrix via linear discriminant projection. Our work also provides some insights for future research.

No abstract available.

Many problems can be reduced to the problem of combining multiple clusterings. In this paper, we first summarize different application scenarios of combining multiple clusterings and provide a new perspective of viewing the problem as a categorical clustering problem. We then show the connections between various consensus and clustering criteria and discuss the complexity results of the problem. Finally we propose a new method to determine the final clustering. Experiments on kinship terms and clustering popular music from heterogeneous feature sets show the effectiveness of combining multiple clusterings.

The paper investigates the use of acoustic based features for music information retrieval. Two specific problems are studied: similarity search (searching for music sound files similar to a given music sound file) and emotion detection (detection of emotion in music sounds). The Daubechies wavelet coefficient histograms (Li, T. et al., SIGIR'03, p.282-9, 2003), which consist of moments of the coefficients calculated by applying the Db8 wavelet filter, are combined with the timbral features extracted using the MARSYAS system of G. Tzanctakis and P. Cook (see IEEE Trans. on Speech and Audio Process., vol.10, no.5, p.293-8, 2002) to generate compact music features. For the similarity search, the distance between two sound files is defined to be the Euclidean distance of their normalized representations. Based on the distance measure, the closest sound files to an input sound file are obtained. Experiments on jazz vocal and classical sound files achieve a very high level of accuracy. Emotion detection is cast as a multiclass classification problem, decomposed as a multiple binary classification problem, and is resolved with the use of support vector machines trained on the extracted features. Our experiments on emotion detection achieved reasonably accurate performance and provided some insights on future work.

Entropy-type measures for the heterogeneity of clusters have been used for a long time. This paper studies the entropy-based criterion in clustering categorical data. It first shows that the entropy-based criterion can be derived in the formal framework of probabilistic clustering models and establishes the connection between the criterion and the approach based on dissimilarity co-efficients. An iterative Monte-Carlo procedure is then presented to search for the partitions minimizing the criterion. Experiments are conducted to show the effectiveness of the proposed procedure.

Efficient and intelligent music information retrieval is a very important topic of the 21st century. With the ultimate goal of building personal music information retrieval systems, this paper studies the problem of identifying "similar" artists using both lyrics and acoustic data. The approach for using a small set of labeled samples for the seed labeling to build classifiers that improve themselves using unlabeled data is presented. This approach is tested on a data set consisting of 43 artists and 56 albums using artist similarity provided by All Music Guide. Experimental results show that using such an approach the accuracy of artist similarity classifiers can be significantly improved and that artist similarity can be efficiently identified.

Document clustering has long been an important problem in information retrieval. In this paper, we present a new clustering algorithm ASI1 , which uses explicitly modeling of the subspace structure associated with each cluster. ASI simultaneously performs data reduction and subspace identification via an iterative alternating optimization procedure. Motivated from the optimization procedure, we then provide a novel method to determine the number of clusters. We also discuss the connections of ASI with various existential clustering approaches. Finally, extensive experimental results on real data sets show the effectiveness of ASI algorithm.

This paper studies the problem of building multiclass classifiers for tissue classification based on gene expression. The recent development of microarray technologies has enabled biologists to quantify gene expression of tens of thousands of genes in a single experiment. Biologists have begun collecting gene expression for a large number of samples. One of the urgent issues in the use of microarray data is to develop methods for characterizing samples based on their gene expression. The most basic step in the research direction is binary sample classification, which has been studied extensively over the past few years. This paper investigates the next step-multiclass classification of samples based on gene expression. The characteristics of expression data (e.g. large number of genes with small sample size) makes the classification problem more challenging. The process of building multiclass classifiers is divided into two components: (i) selection of the features (i.e. genes) to be used for training and testing and (ii) selection of the classification method. This paper compares various feature selection methods as well as various state-of-the-art classification methods on various multiclass gene expression datasets. Our study indicates that multiclass classification problem is much more difficult than the binary one for the gene expression datasets. The difficulty lies in the fact that the data are of high dimensionality and that the sample size is small. The classification accuracy appears to degrade very rapidly as the number of classes increases. In particular, the accuracy was very low regardless of the choices of the methods for large-class datasets (e.g. NCI60 and GCM). While increasing the number of samples is a plausible solution to the problem of accuracy degradation, it is important to develop algorithms that are able to analyze effectively multiple-class expression data for these special datasets.

Text categorization is an important research area and has been receiving much attention due to the growth of the on-line information and of Internet. Automated text categorization is generally cast as a multi-class classification problem. Much of previous work focused on binary document classification problems. Support vector machines (SVMs) excel in binary classification, but the elegant theory behind large-margin hyperplane cannot be easily extended to multi-class text classification. In addition, the training time and scaling are also important concerns. On the other hand, other techniques naturally extensible to handle multi-class classification are generally not as accurate as SVM. This paper presents a simple and efficient solution to multi-class text categorization. Classification problems are first formulated as optimization via discriminant analysis. Text categorization is then cast as the problem of finding coordinate transformations that reflects the inherent similarity from the data. While most of the previous approaches decompose a multiclass classification problem into multiple independent binary classification tasks, the proposed approach enables direct multi-class classification. By using Generalized Singular Value Decomposition (GSVD), a coordinate transformation that reflects the inherent class structure indicated by the generalized singular values is identified. Extensive experiments demonstrate the efficiency and effectiveness of the proposed approach.

Discriminant analysis is known to learn discriminative feature transformations. We study its use in multiclass classification problems. The performance is tested on a large collection of benchmark datasets.

Content-based music genre classification is a fundamental component of music information retrieval systems and has been gaining importance and enjoying a growing amount of attention with the emergence of digital music on the Internet. Currently little work has been done on automatic music genre classification, and in addition, the reported classification accuracies are relatively low. This paper proposes a new feature extraction method for music genre classification, DWCHs. DWCHs stands for Daubechies Wavelet Coefficient Histograms. DWCHs capture the local and global information of music signals simultaneously by computing histograms on their Daubechies wavelet coefficients. Effectiveness of this new feature and of previously studied features are compared using various machine learning classification algorithms, including Support Vector Machines and Linear Discriminant Analysis. It is demonstrated that the use of DWCHs significantly improves the accuracy of music genre classification.

No abstract available.

MOTIVATION: Class distinction is a supervised learning approach that has been successfully employed in the analysis of high-throughput gene expression data. Identification of a set of genes that predicts differential biological states allows for the development of basic and clinical scientific approaches to the diagnosis of disease. The Independent Consistent Expression Discriminator (ICED) was designed to provide a more biologically relevant search criterion during predictor selection by embracing the inherent variability of gene expression in any biological state. The four components of ICED include (i) normalization of raw data; (ii) assignment of weights to genes from both classes; (iii) counting of votes to determine optimal number of predictor genes for class distinction; (iv) calculation of prediction strengths for classification results. The search criteria employed by ICED is designed to identify not only genes that are consistently expressed at one level in one class and at a consistently different level in another class but identify genes that are variable in one class and consistent in another. The result is a novel approach to accurately select biologically relevant predictors of differential disease states from a small number of microarray samples. RESULTS: The data described herein utilized ICED to analyze the large AML/ALL training and test data set (Golub et al., 1999, Science, 286, 531-537) in addition to a smaller data set consisting of an animal model of the childhood neurodegenerative disorder, Batten disease, generated for this study. Both of the analyses presented herein have correctly predicted biologically relevant perturbations that can be used for disease classification, irrespective of sample size. Furthermore, the results have provided candidate proteins for future study in understanding the disease process and the identification of potential targets for therapeutic intervention.

DNA computation investigates the potential of DNA as a massively parallel computing device. Research is focused on designing parallel computation models executable by DNA based chemical processes and on developing algorithms in the models. L. Adleman (1994) initiated this area of research by presenting a DNA based method for solving the Hamilton Path Problem. That contribution raised the hope that parallel computation by DNA could be used to tackle NP-complete problems which are thought of as intractable. The current realization however, is that NP-complete problems may not be best suited for DNA based (more generally, molecule based) computing. A better subject for DNA computing could be large scale evaluation of parallel computation models. Several proposals have been made in this direction. We overview those methods, discuss technical and theoretical issues involved, and present some possible applications of those methods.

The discovery of frequent sequences in temporal databases is an important data mining problem. Most current work assumes that the database is static, and a database update requires rediscovering all the patterns by scanning the entire old and new database. In this paper, we propose novel techniques for maintaining sequences in the presence of a) database updates, and b) user interaction (e.g. modifying mining parameters). This is a very challenging task, since such updates can invalidate existing sequences or introduce new ones. In both the above scenarios, we avoid re-executing the algorithm on the entire dataset, thereby reducing execution time. Experimental results confirm that our approach results in execution time improvements of up to several orders of magnitude in practice.

Classification algorithms are difficult to apply to sequential examples because there is a vast number of potentially useful features for describing each example.Past work on feature selection has focused on searching the space of all subsets of features, which is intractable for large feature sets.We adapt sequence mining techniques to aEi as a preprocessor to select features for standard classification algorithms such as Naive Bayes and Winnow.Our experiments on three different datasets show that the features produced by our algorithm improve classification accuracy by lo-50%,

It is shown that the PL hierarchy PLH = PL ,\bigcup\limits\, PL PL ,\bigcup\limits\, PL PL PL ,\bigcup\limits\, \cdots$, defined in terms of the Ruzzo--Simon--Tompa relativization, collapses to PL.

Properties of (unbounded-error) probabilistic as well as “probabilistic plus nondeterministic” pushdown automata and auxiliary pushdown automata are studied. These models are analogous to their counterparts with nondeterministic and alternating states. Complete characterizations in terms of well-known complexity classes are given for the classes of languages recognized by polynomial time-bounded, logarithmic space-bounded auxiliary pushdown automata with probabilistic states and with “probabilistic plus nondeterministic” states. Also, complexity lower bounds are given for the classes of languages recognized by these automata with unlimited running time. It follows that, by fixing an appropriate mode of computation, the difference between classes of languages such as P and PSPACE, NL and SAC1, PL and Diff>(#SAC1) is characterized as the difference between the number of stack symbols; that is, whether the stack alphabet contains one versus two distinct symbols.

We demonstrate that DNA computers can simulate Boolean circuits with a small overhead. Boolean circuits embody the notion of massively parallel signal processing and are frequently encountered in many parallel algorithms. Many important problems such as sorting, integer arithmetic, and matrix multiplication are known to be computable by small size Boolean circuits much faster than by ordinary sequential digital computers. This paper shows that DNA chemistry allows one to simulate large semi-unbounded fan-in Boolean circuits with a logarithmic slowdown in computation time. Also, for the class NC$^1$, the slowdown can be reduced to a constant. In this algorithm we have encoded the inputs, the Boolean AND gates, and the OR gates to DNA oligonucleotide sequences. We operate on the gates and the inputs by standard molecular techniques of sequence-specific annealing, ligation, separation by size, limited amplification, sequence-specific cleavage, and detection by size. Preliminary biochemical experiments on a small test circuit have produced encouraging results. Further confirmatory experiments are in progress.

Cai and Furst proved that every PSPACE language can be solved via a large number of identical simple tasks, each of which is provided with the original input, its own unique task number, and at most three bits of output from the previous task. In the Cai–Furst model, the tasks are required to be run in the order specified by the task numbers. To study the extent to which the Cai–Furst PSPACE result is due to this strict scheduling, we remove their ordering restriction, allowing tasks to execute in any serial order. That is, we study the extent to which complex tasks can be decomposed into large numbers of simple tasks that can be scheduled arbitrarily. We provide upper bounds on the complexity of the sets thus accepted. Our bounds suggest that Cai and Furst's surprising PSPACE result is due in large part to the fixed order of their task execution. In fact, our bounds suggest the possibility that even relatively low levels of the polynomial hierarchy cannot be accepted via large numbers of simple tasks that can be scheduled arbitrarily. However, adding randomization recaptures the polynomial hierarchy. The entire polynomial hierarchy can be accepted by large numbers of arbitrarily scheduled probabilistic tasks passing only a single bit of information between successive tasks (and using J. Simon's “exact counting” acceptance mechanism). In fact, we show that the class of languages so accepted is exactly NPPP.

This paper focuses on complexity classes of partial functions that are computed in polynomial time with oracles in NPMV, the class of all multivalued partial functions that are computable nondeterministically in polynomial time. Concerning deterministic polynomial-time reducibilities, it is shown that a multivalued partial function is polynomial-time computable with k adaptive queries to NPMV if and only if it is polynomial-time computable via 2 k-1 nonadaptive queries to NPMV; a characteristic function is polynomial-time computable with k adaptive queries to NPMV if and only if it is polynomial-time computable with k adaptive queries to NP; unless the Boolean hierarchy collapses, for every k, k adaptive (nonadaptive) queries to NPMV are different than k+1 adaptive (nonadaptive) queries to NPMV. Nondeterministic reducibilities, lowness, and the difference hierarchy over NPMV are also studied. The difference hierarchy for partial functions does not collapse unless the Boolean hierarchy collapses, but, surprisingly, the levels of the difference and bounded query hierarchies do not interleave (as is the case for sets) unless the polynomial hierarchy collapses.

Data mining is an emerging research area, whose goal is to extract significant patterns or interesting rules from large databases. High-level inference from large volumes of routine business data can provide valuable information to businesses, such as customer buying patterns, shelving criterion in supermarkets and stock trends. Many algorithms have been proposed for data mining of association rules. However, research so far has mainly focused on sequential algorithms. In this paper we present parallel algorithms for data mining of association rules, and study the degree of parallelism, synchronization, and data locality issues on the SGI Power Challenge shared-memory multi-processor. We further present a set of optimizations for the sequential and parallel algorithms.Experiments show that a significant improvement of performance is achieved using our proposed optimizations. We also achieved good speed-up for the parallel algorithm, but we observe a need for parallel I/O techniques for further performance gains.

ComplexityClasses for Counting and Enumeration

Article Free Access Share on The PL hierarchy collapses Author: Mitsunori Ogihara Department of Computer Science, University of Rochester, Rochester, NY Department of Computer Science, University of Rochester, Rochester, NYView Profile Authors Info & Claims STOC '96: Proceedings of the twenty-eighth annual ACM symposium on Theory of ComputingJuly 1996 Pages 84–88https://doi.org/10.1145/237814.237834Published:01 July 1996Publication History 6citation251DownloadsMetricsTotal Citations6Total Downloads251Last 12 Months16Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

We distinguish self-reducibility of a languageLwith the question of whether search reduces to decision forL. Results include: (i) If NE≠E, then there exists a setLin NP−P such that search reduces to decision forL, search doesnotnonadaptively reduce to decision forLandLis not self-reducible. (ii) If UE≠E, then there exists a languageL∈UP−P such that search nonadaptively reduces to decision for L, but L is not self-reducible. (iii) If UE∩co-UE≠E, then there is a disjunctive self-reducible languageL∈UP−P for which search doesnotnonadaptively reduce to decision. We prove that if NE⊈BPE, then there is a languageL∈NP−BPP such thatLis randomly self-reducible,notnonadaptively randomly self-reducible, andnotself-reducible. We obtain results concerning trade-offs in multiprover interactive proof systems and results that distinguish checkable languages from those that are nonadaptively checkable. Many of our results are proven by constructing p-selective sets. We obtain a p-selective set that isnot⩽Ptt-equivalent to any tally language, and we show that if P=PP, then every p-selective set is ⩽PT-equivalent to a tally language. Similarly, if P=NP, then every cheatable set is ⩽Pm-equivalent to a tally language. We construct a recursive p-selective tally set that isnotcheatable.

For any operatorτon integer-valued functions, we say that #P isclosed under τ in the context ofPF∘#P if, for everyf∈#P,τ[f] belongs to PF∘num;P. For several operatorsτ, it is shown that the closure properties of #P underτin the above sense is closely related to the relationships between P#P[1]and higher classes such as PHPPand PPPP.

Is there an NP function that, when given a satisfiable formula as input, outputs one satisfying assignment uniquely? That is, can a nondeterministic function cull just one satisfying assignment from a possibly exponentially large collection of assignments? We show that if there is such a nondeterministic function, then the polynomial hierarchy collapses to ${\text{ZPP}}^{{\text{NP}}} $ (and thus, in particular, to ${\text{NP}}^{{\text{NP}}} $). Because the existence of such a function is known to be equivalent to the statement “every NP function has an NP refinement with unique outputs,” our result provides the strongest evidence yet that NP functions cannot be refined. We prove our result via a result of independent interest. We say that a set A is NPSV-selective (NPMV-selective) if there is a 2-ary partial NP function with unique values (a 2-ary partial NP function) that decides which of its inputs (if any) is “more likely” to belong to A; this is a nondeterministic analog of the recursion-theoretic notion of the semirecursive sets and the extant complexity-theoretic notion of P-selectivity. Our hierarchy-collapse result follows by combining the easy observation that every set in NP is NPMV-selective with the following result: If $A \in {\text{NP}}$ is NPSV-selective, then $A \in {{({\text{NP}} \cap {\text{coNP}})} / {{\text{poly}}}}$. Relatedly, we prove that if $A \in {\text{NP}}$ is NPSV-selective, then A is ${\text{Low}}_2 $. We prove that the polynomial hierarchy collapses even further, namely to NP, if all coNP sets are NPMV-selective. This follows from a more general result we prove: Every self-reducible NPMV-selective set is in NP.

A set is P-selective (Selman, 1979) if there is a polynomial-time semidecision algorithm for the set — an algorithm that given any two strings decides which is “more likely” to be in the set. This paper establishes a strict hierarchy among the various reductions and equivalences to P-selective sets.

J. Hartmanis (1978) conjectured that there exist no sparse complete sets for P under logspace many-one reductions. In this paper, in support of the conjecture, it is shown that if P has sparse hard sets under logspace many-one reductions, then P/spl sube/DSPACE[log/sup 2/n]. The result follows from a more general statement: if P has 2/sup polylog/ sparse hard sets under poly-logarithmic space-computable many-one reductions, then P/spl sube/DSPACE[polylog].

Gottlob (1993, in "Proceedings, 34th IEEE Symposium on Foundations of Computer Science," pp. 42-51) showed that any set recognized by polynomial-size, log-depth trees with queries to SAT is ≤ptt-reducible to NP. Based on his technique, it is shown for any set A and any k ≥ 1 that NCk (A) ⊆ ACk − 1(RNPctt(A)) where RNPctt(A) is the ≤NPctt-closure of A. As a consequence, it is shown for any class C that is closed under ≤NPctt-reductions, such as NP and C=P, and for any k ≥ 1 that NCk(C) = ACk − 1 (C), which resolves a question that has remained open for a long time.

It is shown for any prime power k, that the class of languages recognized by robust oracle Turing machines that are P-helped by MOD_kP coincides with the class MOD_kP.

This paper studies a notion called polynomial-time membership comparable sets. For a function g, a set A is polynomial-time g-membership comparable if there is a polynomial-time computable function f such that for any $x_{ 1}, \dotsc , x_{m}$ with $m \geq g(\max \{|x_{1}|, \dotsc, |x_{m}|\})$, f outputs $b \in \{0,1\}^{m}$ such that $(A (x_{1}), \dotsc , A (x_{m})) \neq b$. The following is a list of major results proven in the paper: 1. Polynomial-time membership comparable sets construct a proper hierarchy according to the bound on the number of arguments. 2. Polynomial-time membership comparable sets have polynomial-size circuits. 3. For any function f and any constant $c > 0$, if a set is $\leq_{f(n)-tt}^{p}$-reducible to a P-selective set:, then the set is polynomial-time $(1 + c) \log f(n)$-membership comparable. 4. For any $\mathcal{C}$ chosen from $\{ {\text{PSPACE}},{\text{UP}},{\text{FewP}},{\text{NP}},{\text{C}}_ {=} {\text{P}},{\text{PP}},{\text{MOD}}_{2} {\text{P}},{\text{MOD}}_{3} {\text{P}}, \dotsc \} $, if $\mathcal{C} \subseteq {\text{P-mc}}(c \log n)$ for some $c < 1$, then $\mathcal{C} = {\text{P}}$. As a corollary of the last two results, it is shown that if there is some constant $c < 1$ such that all $\mathcal{C}$ are polynomial-time $n^{c}$-truth-table reducible to some P-selective sets, then $\mathcal{C} = P$, which resolves a question that has been leftft open for a long time.

For various polynomial-time reducibilities r, this paper asks whether being r-reducible to a sparse set is a broader notion than being r-equivalent to a sparse set. Although distinguishing equivalence and reducibility to sparse sets, for many-one or 1-truth-table reductions, would imply that $P \ne NP$, this paper shows that for k-truth-table reductions, $k \geq 2$, equivalence and reducibility to sparse sets provably differ. Though Gavaldà and Watanabe have shown that, for any polynomial-time computable unbounded function $f( \cdot )$, some sets $f(n)$-truth-table reducible to sparse sets are not even Turing equivalent to sparse sets, this paper shows that extending their result to the 2-truth-table case would provide a proof that $P\ne NP$. Additionally, this paper studies the relative power of different notions of reducibility, and proves that disjunctive and conjunctive truth-table reductions to sparse sets are surprisingly powerful, refuting a conjecture of Ko.

In this paper, it is shown that many natural counting classes, such as PP, $C_ = P$, and ${\text{MOD}}_k {\text{P}}$, are at least as computationally hard as PH (the polynomial-time hierarchy) in the following sense: for each ${\bf K}$ of the counting classes above, every set in ${\bf K}$(PH) is polynomial-time randomized many-one reducible to a set in ${\bf K}$ with two-sided exponentially small error probability. As a consequence of the result, it is seen that all the counting classes above are computationally harder than PH unless PH collapses to a finite level. Some other consequences are also shown.

It is proved that if ${\text{P}} \ne {\text{NP}}$, then there exists a set in ${\text{NP}}$ that is not polynomial-time bounded truth-table reducible (in short, $ \leqq _{{\text{btt}}}^{\text{P}} $-reducible) to any sparse set. In other words, it is proved that no sparse $ \leqq _{{\text{btt}}}^{\text{P}} $-hard set exists for ${\text{NP}}$ unless ${\text{P}} = {\text{NP}}$. By using the technique proving this result, the intractability of several number-theoretic decision problems, i.e., decision problems defined naturally from number-theoretic problems is investigated. It is shown that for these number-theoretic decision problems, if it is not in ${\text{P}}$, then it is not $ \leqq _{{\text{btt}}}^{\text{P}} $-reducible to any sparse set.

We prove that if P ¢ NP, then there exists a set in NP that is polynomial time bounded truth-table reducible (in short, <Ptt-reducible) to no sparse set.In other words, we prove that no sparse <bPtt-hard set exists for NP unless P = NP.By using the technique proving this result, we investigate intractability of several number theoretic decision problems, i.e., decision problems defined naturally from number theoretic problems.We show that for those number theoretic decision problems, if it is not in P, then it is <~tt-reducible to no sparse set.