CiteSeerX Scientific Literature Digital Library and Search Engine
CiteSeerX is a scientific literature digital library and search engine that focuses primarily on the literature in computer and information science. CiteSeerx aims to improve the dissemination of scientific literature and to provide improvements in functionality, usability, availability, cost, comprehensiveness, efficiency, and timeliness in the access of scientific and scholarly knowledge
One-Way Communication Complexity of Symmetric Boolean Functions - Jan Arpe; Andreas Jakoby; Maciej Liskiewicz
We study deterministic one-way communication complexity of functions with Hankel communication matrices. Some structural properties of such matrices are established and applied to the one-way two-party communication complexity of symmetric Boolean functions. It is shown that the number of required communication bits does not depend on the communication direction, provided that neither direction needs maximum complexity. Moreover, in order to obtain an optimal protocol, it is in any case sufficient to consider only the communication direction from the party with the shorter input to the other party. These facts do not hold for arbitrary Boolean functions in general. Next, gaps...
The risk profile problem for stock portfolio optimization (Extended Abstract) - Ming-yang Kao; Andreas Nolte; Stephen R. Tate
In this paper we study the problem of determining an optimal investment strategy for investors with different attitudes towards the trade-offs of risk and profit. The probability distribution of the return values of the stocks that are considered by the investor are assumed to be known, while the joint distribution is unknown. The problem is to find the best investment strategy in order to minimize the probability of losing a certain percentage of the invested capital based on different attitudes of the investors towards future outcomes of the stock market. We show that for portfolios made up of two stocks,...
Search Problems in the Decision Tree Model - László Lovász; Moni Naor; Ilan Newman; Avi Wigderson
We study the relative power of determinism, randomness and nondeterminism for search problems in the Boolean decision tree model. We show that the gaps between the nondeterministic, the randomized and the deterministic complexities can be arbitrary large for search problems. We also mention an interesting connection of this model to the complexity of resolution proofs.
Convex Quadrilaterals and k-Sets - Emo Welzl
We prove that the minimum number of convex quadrilaterals determined by n points in general position in the plane- or in other words, the rectilinear crossing number of the complete graph Kn- is at least (
An algebraic matching algorithm - James F. Geelen
It is not immediately clear how to obtain an efficient matching algorithm from the Tutte matrix. The determinant of T is a polynomial that may have exponentially many terms, so it cannot be computed efficiently. We circumvent this problem by substituting constants in place of the indeterminates. In doing so the rank of T does not increase. This idea was originally proposed by Lov'asz  who gave an efficient randomized algorithm for finding
Causal Nets or What Is a Deterministic Computation? - Péter Gács; Leonid A. Levin
The network approach to computation is more direct and “physical” than the one based on some specific computing devices (like Turing machines). However, the size of a usual—e.g., Boolean—network does not reflect the complexity of computing the corresponding function, since a small network may be very hard to find even if it exists. A history of the work of a particular computing device can be described as a network satisfying some restrictions. The size of this network reflects the complexity of the problem, but the restrictions are usually somewhat arbitrary and even awkward. Causal nets are restricted only by determinism...
On randomly colouring locally sparse graphs - Alan Frieze; Juan Vera
We consider the problem of generating a random q-colouring of a graph G = (V, E). We consider the simple Glauber Dynamics chain. We show that if for all v ∈ V the average degree of the subgraph Hv induced by the neighbours of v ∈ V is ≪ ∆ where ∆ is the maximum degree and ∆> c1 ln n then for sufficiently large c1, this chain mixes rapidly provided q/ ∆> α, where α ≈ 1.763 is the root of α = e 1/α. For this class of graphs, which includes planar graphs, triangle free graphs and random...
Spectral Clustering of Biological Sequence Data - William Pentney; Marina Meila
In this paper, we apply spectral techniques to clustering biological sequence data that has proved more difficult to cluster effectively. For this purpose, we have to (1) extend spectral clustering algorithms to deal with asymmetric affinities, like the alignment scores used in the comparison of biological sequences, and (2) devise a hierarchical algorithm that can handle many clusters with imbalanced sizes robustly. We present an algorithm for clustering asymmetric affinity data, and demonstrate the performance of this algorithm at recovering the higher levels of the Structural Classification of Proteins (SCOP) on a data base of highly conserved subsequences.
The Poincaré Constant of a Random Walk in High-Dimensional Convex Bodies - Ivona Bezáková
Estimating the volume of a convex body is an important algorithmic problem. High dimensions pose an especially difficult task for the algorithm designer. To be considered efficient, the running time must be polynomial in the dimension. The first provably efficient approximation algorithm was presented by Dyer, Frieze and Kannan in 1989, and steadily improved by various authors over the next decade. Fundamental to these works is the analysis of random walks for generating a random point from a convex body. Kannan,
Random Walks And An O*(n⁵) Volume Algorithm For Convex Bodies - Ravi Kannan; László Lovász; Miklos Simonovits
Given a high dimensional convex body K ` IR n by a separation oracle, we can approximate its volume with relative error ", using O (n⁵) oracle calls. Our algorithm also brings the body into isotropic position. As all previous randomized volume algorithms, we use "rounding" followed by a multiphase Monte-Carlo (product estimator) technique. Both parts rely on sampling (generating random points in K), which is done by random walk. Our algorithm introduces three new ideas: ffl the use of the isotropic position (or at least an approximation of it) for rounding, ffl the separation of global obstructions (diameter) and...
An Exponential Lower Bound on the Size of Algebraic Decision Trees for MAX - D. Grigoriev; M. Karpinski; A. C. Yao
We prove an exponential lower bound on the size of any fixed-degree algebraic decision tree for solving MAX, the problem of finding the maximum of n real numbers. This complements the n - 1 lower bound of Rabin [R72] on the depth of algebraic decision trees for this problem. The proof in fact gives an exponential lower bound on size for the polyhedral decision problem MAX= of testing whether the j-th number is the maximum among a list of n real numbers. Previously, except for linear decision trees, no nontrivial lower bounds on the size of algebraic decision trees for...
On (G) (G) > 0 gap recognition and (G)-upper bounds - Stanislav Busygin; Dmitrii V. Pasechnik
We show that for a graph G it is NP -hard to decide whether its independence number (G) equals its clique partition number (G) even when some minimum clique partition of G is given. This implies that any (G)-upper bound provably better than (G) is NP -hard to compute.
Space-efficient Approximation Algorithms for MAXCUT and COLORING Semidefinite Programs - Philip Klein; Hsueh-I Lu
The essential part of the best known approximation algorithm for graph MAXCUT is approximately solving MAXCUT's semidefinite relaxation. For a graph with n nodes and m edges, previous work on solving its semidefinite relaxation for MAXCUT requires space ~ O(n²). We show how an approximate solution can be found in space O(m+n 1:5 ), where O(m) comes from the input; and therefore reduce the space required by the best known approximation algorithm for graph MAXCUT. Using the above space-efficient algorithm as a subroutine, we show an approximate solution for COLORING's semidefinite relaxation can be found in space O(m)+ ~ O(n...
On Derandomized Approximation Algorithms - Anand Srivastav; Peter Stangier
With the design of powerful randomized algorithms the transformation of a randomized algorithm or probabilistic existence result for combinatorial problems into an efficient deterministic algorithm (called derandomization) became an important issue in algorithmic discrete mathematics. In the last years several interesting examples of derandomization have been published, like discrepancy in hypergraph colouring, packing integer programs and an algorithmic version of the Lovász-Local-Lemma. In this paper the derandomization method of conditional probabilities of Raghavan /Spencer is extended using discrete martingales. As a main result pessimistic estimators are constructed for combinatorial approximation problems involving non-linear objective functions with bounded martingale differences. The...
On Bisubmodular Maximization - Ajit P. Singh; Andrew Guillory; Jeff Bilmes
Bisubmodularity extends the concept of submodularity to set functions with two arguments. We show how bisubmodular maximization leads to richer value-of-information problems, using examples in sensor placement and feature selection. We present the first constant-factor approximation algorithm for a wide class of bisubmodular maximizations.
Learning mixtures of submodular shells with application to document summarization - Hui Lin; Jeff Bilmes
We introduce a method to learn a mixture of submodular “shells” in a large-margin setting. A submodular shell is an abstract submodular function that can be instantiated with a ground set and a set of parameters to produce a submodular function. A mixture of such shells can then also be so instantiated to produce a more complex submodular function. What our algorithm learns are the mixture weights over such shells. We provide a risk bound guarantee when learning in a large-margin structured-prediction setting using a projected subgradient method when only approximate submodular optimization is possible (such as with submodular function...
CONTEXT MANAGEMENT IN COMMUNITY CENTRIC SERVICE ENVIRONMENT - Jani Pellikka
In both mobile and desktop environments, context information has gained a strong foothold in the form of location and user presence. This information characterising the situation of an entity has been widely used in various systems to make services to adapt and behave according to the state of their users. The emerging of virtual communities, however, brings new aspects to the context information studies. Mobile communities, representing the next evolutionary step of virtual communities, are of a particular interest as they can be seen to foster new kind of community services, where the context information of whole memberships will be...