OpenRaiser/Intern-Atlas huggingface dataset:
Statistical mechanics of budget-constrained auctions
Venue: arXiv cs.GT 2009
Year: 2009

Finding the optimal assignment in budget-constrained auctions is a combinatorial optimization problem with many important applications, a notable example being the sale of advertisement space by search engines (in this context the problem is often referred to as the off-line AdWords problem). Based on the cavity method of statistical mechanics, we introduce a message passing algorithm that is capable of solving efficiently random instances of the problem extracted from a natural distribution, and we derive from its properties the phase diagram of the problem. As the control parameter (average value of the budgets) is varied, we find two phase transitions delimiting a region in which long-range correlations arise.
CloudSim: A Novel Framework for Modeling and Simulation of Cloud Computing Infrastructures and Services
Venue: arXiv cs.DC 2009
Year: 2009

Cloud computing focuses on delivery of reliable, secure, fault-tolerant, sustainable, and scalable infrastructures for hosting Internet-based application services. These applications have different composition, configuration, and deployment requirements. Quantifying the performance of scheduling and allocation policy on a Cloud infrastructure (hardware, software, services) for different application and service models under varying load, energy performance (power consumption, heat dissipation), and system size is an extremely challenging problem to tackle. To simplify this process, in this paper we propose CloudSim: a new generalized and extensible simulation framework that enables seamless modelling, simulation, and experimentation of emerging Cloud computing infrastructures and management services. The simulation framework has the following novel features: (i) support for modelling and instantiation of large scale Cloud computing infrastructure, including data centers on a single physical computing node and java virtual machine; (ii) a self-contained platform for modelling data centers, service brokers, scheduling, and allocations policies; (iii) availability of virtualization engine, which aids in creation and management of multiple, independent, and co-hosted virtualized services on a data center node; and (iv) flexibility to switch between space-shared and time-shared allocation of processing cores to virtualized services.
A Pseudo DNA Cryptography Method
Venue: arXiv cs.CR 2009
Year: 2009

The DNA cryptography is a new and very promising direction in cryptography research. DNA can be used in cryptography for storing and transmitting the information, as well as for computation. Although in its primitive stage, DNA cryptography is shown to be very effective. Currently, several DNA computing algorithms are proposed for quite some cryptography, cryptanalysis and steganography problems, and they are very powerful in these areas. However, the use of the DNA as a means of cryptography has high tech lab requirements and computational limitations, as well as the labor intensive extrapolation means so far. These make the efficient use of DNA cryptography difficult in the security world now. Therefore, more theoretical analysis should be performed before its real applications. In this project, We do not intended to utilize real DNA to perform the cryptography process; rather, We will introduce a new cryptography method based on central dogma of molecular biology. Since this method simulates some critical processes in central dogma, it is a pseudo DNA cryptography method. The theoretical analysis and experiments show this method to be efficient in computation, storage and transmission; and it is very powerful against certain attacks. Thus, this method can be of many uses in cryptography, such as an enhancement insecurity and speed to the other cryptography methods. There are also extensions and variations to this method, which have enhanced security, effectiveness and applicability.
The Secrecy Capacity Region of the Gaussian MIMO Multi-receiver Wiretap Channel
Venue: arXiv cs.IT 2009
Year: 2009

In this paper, we consider the Gaussian multiple-input multiple-output (MIMO) multi-receiver wiretap channel in which a transmitter wants to have confidential communication with an arbitrary number of users in the presence of an external eavesdropper. We derive the secrecy capacity region of this channel for the most general case. We first show that even for the single-input single-output (SISO) case, existing converse techniques for the Gaussian scalar broadcast channel cannot be extended to this secrecy context, to emphasize the need for a new proof technique. Our new proof technique makes use of the relationships between the minimum-mean-square-error and the mutual information, and equivalently, the relationships between the Fisher information and the differential entropy. Using the intuition gained from the converse proof of the SISO channel, we first prove the secrecy capacity region of the degraded MIMO channel, in which all receivers have the same number of antennas, and the noise covariance matrices can be arranged according to a positive semi-definite order. We then generalize this result to the aligned case, in which all receivers have the same number of antennas, however there is no order among the noise covariance matrices. We accomplish this task by using the channel enhancement technique. Finally, we find the secrecy capacity region of the general MIMO channel by using some limiting arguments on the secrecy capacity region of the aligned MIMO channel. We show that the capacity achieving coding scheme is a variant of dirty-paper coding with Gaussian signals.
Markov Random Field Segmentation of Brain MR Images
Venue: arXiv cs.CV 2009
Year: 2009

We describe a fully-automatic 3D-segmentation technique for brain MR images. Using Markov random fields the segmentation algorithm captures three important MR features, i.e. non-parametric distributions of tissue intensities, neighborhood correlations and signal inhomogeneities. Detailed simulations and real MR images demonstrate the performance of the segmentation algorithm. The impact of noise, inhomogeneity, smoothing and structure thickness is analyzed quantitatively. Even single echo MR images are well classified into gray matter, white matter, cerebrospinal fluid, scalp-bone and background. A simulated annealing and an iterated conditional modes implementation are presented. Keywords: Magnetic Resonance Imaging, Segmentation, Markov Random Fields
On Generalized Minimum Distance Decoding Thresholds for the AWGN Channel
Venue: arXiv cs.IT 2009
Year: 2009

We consider the Additive White Gaussian Noise channel with Binary Phase Shift Keying modulation. Our aim is to enable an algebraic hard decision Bounded Minimum Distance decoder for a binary block code to exploit soft information obtained from the demodulator. This idea goes back to Forney and is based on treating received symbols with low reliability as erasures. This erasing at the decoder is done using a threshold, each received symbol with reliability falling below the threshold is erased. Depending on the target overall complexity of the decoder this pseudo-soft decision decoding can be extended from one threshold T to z>1 thresholds T_1<...<T_z for erasing received symbols with lowest reliability. The resulting technique is widely known as Generalized Minimum Distance decoding. In this paper we provide a means for explicit determination of the optimal threshold locations in terms of minimal decoding error probability. We do this for the one and the general z>1 thresholds case, starting with a geometric interpretation of the optimal threshold location problem and using an approach from Zyablov.
The Secrecy Capacity Region of the Gaussian MIMO Broadcast Channel
Venue: arXiv cs.IT 2009
Year: 2009

In this paper, we consider a scenario where a source node wishes to broadcast two confidential messages for two respective receivers via a Gaussian MIMO broadcast channel. A wire-tapper also receives the transmitted signal via another MIMO channel. First we assumed that the channels are degraded and the wire-tapper has the worst channel. We establish the capacity region of this scenario. Our achievability scheme is a combination of the superposition of Gaussian codes and randomization within the layers which we will refer to as Secret Superposition Coding. For the outerbound, we use the notion of enhanced channel to show that the secret superposition of Gaussian codes is optimal. We show that we only need to enhance the channels of the legitimate receivers, and the channel of the eavesdropper remains unchanged. Then we extend the result of the degraded case to non-degraded case. We show that the secret superposition of Gaussian codes along with successive decoding cannot work when the channels are not degraded. we develop a Secret Dirty Paper Coding (SDPC) scheme and show that SDPC is optimal for this channel. Finally, we investigate practical characterizations for the specific scenario in which the transmitter and the eavesdropper have multiple antennas, while both intended receivers have a single antenna. We characterize the secrecy capacity region in terms of generalized eigenvalues of the receivers channel and the eavesdropper channel. We refer to this configuration as the MISOME case. In high SNR we show that the capacity region is a convex closure of two rectangular regions.
Fault-Tolerant Consensus in Unknown and Anonymous Networks
Venue: arXiv cs.DS 2009
Year: 2009

This paper investigates under which conditions information can be reliably shared and consensus can be solved in unknown and anonymous message-passing networks that suffer from crash-failures. We provide algorithms to emulate registers and solve consensus under different synchrony assumptions. For this, we introduce a novel pseudo leader-election approach which allows a leader-based consensus implementation without breaking symmetry.
Comment on "Language Trees and Zipping" arXiv:cond-mat/0108530
Venue: arXiv cs.AI 2009
Year: 2009

Every encoding has priori information if the encoding represents any semantic information of the unverse or object. Encoding means mapping from the unverse to the string or strings of digits. The semantic here is used in the model-theoretic sense or denotation of the object. If encoding or strings of symbols is the adequate and true mapping of model or object, and the mapping is recursive or computable, the distance between two strings (text) is mapping the distance between models. We then are able to measure the distance by computing the distance between the two strings. Otherwise, we may take a misleading course. "Language tree" may not be a family tree in the sense of historical linguistics. Rather it just means the similarity.
Towards a decentralized algorithm for mapping network and computational resources for distributed data-flow computations
Venue: arXiv cs.DC 2009
Year: 2009

Several high-throughput distributed data-processing applications require multi-hop processing of streams of data. These applications include continual processing on data streams originating from a network of sensors, composing a multimedia stream through embedding several component streams originating from different locations, etc. These data-flow computing applications require multiple processing nodes interconnected according to the data-flow topology of the application, for on-stream processing of the data. Since the applications usually sustain for a long period, it is important to optimally map the component computations and communications on the nodes and links in the network, fulfilling the capacity constraints and optimizing some quality metric such as end-to-end latency. The mapping problem is unfortunately NP-complete and heuristics have been previously proposed to compute the approximate solution in a centralized way. However, because of the dynamicity of the network, it is practically impossible to aggregate the correct state of the whole network in a single node. In this paper, we present a distributed algorithm for optimal mapping of the components of the data flow applications. We propose several heuristics to minimize the message complexity of the algorithm while maintaining the quality of the solution.
Tree decomposition and postoptimality analysis in discrete optimization
Venue: arXiv cs.DM 2009
Year: 2009

Many real discrete optimization problems (DOPs) are $NP$-hard and contain a huge number of variables and/or constraints that make the models intractable for currently available solvers. Large DOPs can be solved due to their special tructure using decomposition approaches. An important example of decomposition approaches is tree decomposition with local decomposition algorithms using the special block matrix structure of constraints which can exploit sparsity in the interaction graph of a discrete optimization problem. In this paper, discrete optimization problems with a tree structural graph are solved by local decomposition algorithms. Local decomposition algorithms generate a family of related DO problems which have the same structure but differ in the right-hand sides. Due to this fact, postoptimality techniques in DO are applied.
On the Achievable Rate of the Fading Dirty Paper Channel with Imperfect CSIT
Venue: arXiv cs.IT 2009
Year: 2009

The problem of dirty paper coding (DPC) over the (multi-antenna) fading dirty paper channel (FDPC) Y = H(X + S) + Z is considered when there is imperfect knowledge of the channel state information H at the transmitter (CSIT). The case of FDPC with positive definite (p.d.) input covariance matrix was studied by the authors in a recent paper, and here the more general case of positive semi-definite (p.s.d.) input covariance is dealt with. Towards this end, the choice of auxiliary random variable is modified. The algorithms for determination of inflation factor proposed in the p.d. case are then generalized to the case of p.s.d. input covariance. Subsequently, the largest DPC-achievable high-SNR (signal-to-noise ratio) scaling factor over the no-CSIT FDPC with p.s.d. input covariance matrix is derived. This scaling factor is seen to be a non-trivial generalization of the one achieved for the p.d. case. Next, in the limit of low SNR, it is proved that the choice of all-zero inflation factor (thus treating interference as noise) is optimal in the 'ratio' sense, regardless of the covariance matrix used. Further, in the p.d. covariance case, the inflation factor optimal at high SNR is obtained when the number of transmit antennas is greater than the number of receive antennas, with the other case having been already considered in the earlier paper. Finally, the problem of joint optimization of the input covariance matrix and the inflation factor is dealt with, and an iterative numerical algorithm is developed.
On Decidability Properties of One-Dimensional Cellular Automata
Venue: arXiv cs.LO 2009
Year: 2009

In a recent paper Sutner proved that the first-order theory of the phase-space $\mathcal{S}_\mathcal{A}=(Q^\mathbb{Z}, \longrightarrow)$ of a one-dimensional cellular automaton $\mathcal{A}$ whose configurations are elements of $Q^\mathbb{Z}$, for a finite set of states $Q$, and where $\longrightarrow$ is the "next configuration relation", is decidable. He asked whether this result could be extended to a more expressive logic. We prove in this paper that this is actuallly the case. We first show that, for each one-dimensional cellular automaton $\mathcal{A}$, the phase-space $\mathcal{S}_\mathcal{A}$ is an omega-automatic structure. Then, applying recent results of Kuske and Lohrey on omega-automatic structures, it follows that the first-order theory, extended with some counting and cardinality quantifiers, of the structure $\mathcal{S}_\mathcal{A}$, is decidable. We give some examples of new decidable properties for one-dimensional cellular automata. In the case of surjective cellular automata, some more efficient algorithms can be deduced from results of Kuske and Lohrey on structures of bounded degree. On the other hand we show that the case of cellular automata give new results on automatic graphs.
Guaranteed Minimum Rank Approximation from Linear Observations by Nuclear Norm Minimization with an Ellipsoidal Constraint
Venue: arXiv cs.IT 2009
Year: 2009

The rank minimization problem is to find the lowest-rank matrix in a given set. Nuclear norm minimization has been proposed as an convex relaxation of rank minimization. Recht, Fazel, and Parrilo have shown that nuclear norm minimization subject to an affine constraint is equivalent to rank minimization under a certain condition given in terms of the rank-restricted isometry property. However, in the presence of measurement noise, or with only approximately low rank generative model, the appropriate constraint set is an ellipsoid rather than an affine space. There exist polynomial-time algorithms to solve the nuclear norm minimization with an ellipsoidal constraint, but no performance guarantee has been shown for these algorithms. In this paper, we derive such an explicit performance guarantee, bounding the error in the approximate solution provided by nuclear norm minimization with an ellipsoidal constraint.
Asymptotic Optimality of the Static Frequency Caching in the Presence of Correlated Requests
Venue: arXiv cs.PF 2009
Year: 2009

It is well known that the static caching algorithm that keeps the most frequently requested documents in the cache is optimal in case when documents are of the same size and requests are independent and equally distributed. However, it is hard to develop explicit and provably optimal caching algorithms when requests are statistically correlated. In this paper, we show that keeping the most frequently requested documents in the cache is still optimal for large cache sizes even if the requests are strongly correlated.
A Novel Algorithm for Compressive Sensing: Iteratively Reweighed Operator Algorithm (IROA)
Venue: arXiv cs.IT 2009
Year: 2009

Compressive sensing claims that the sparse signals can be reconstructed exactly from many fewer measurements than traditionally believed necessary. One of issues ensuring the successful compressive sensing is to deal with the sparsity-constraint optimization. Up to now, many excellent theories, algorithms and software have been developed, for example, the so-called greedy algorithm ant its variants, the sparse Bayesian algorithm, the convex optimization methods, and so on. The formulations for them consist of two terms, in which one is and the other is (, mostly, p=1 is adopted due to good characteristic of the convex function) (NOTE: without the loss of generality, itself is assumed to be sparse). It is noted that all of them specify the sparsity constraint by the second term. Different from them, the developed formulation in this paper consists of two terms where one is with () and the other is . For each iteration the measurement matrix (linear operator) is reweighed by determined by which is obtained in the previous iteration, so the proposed method is called the iteratively reweighed operator algorithm (IROA). Moreover, in order to save the computation time, another reweighed operation has been carried out; in particular, the columns of corresponding to small have been excluded out. Theoretical analysis and numerical simulations have shown that the proposed method overcomes the published algorithms.
Flow of Activity in the Ouroboros Model
Venue: arXiv cs.AI 2009
Year: 2009

The Ouroboros Model is a new conceptual proposal for an algorithmic structure for efficient data processing in living beings as well as for artificial agents. Its central feature is a general repetitive loop where one iteration cycle sets the stage for the next. Sensory input activates data structures (schemata) with similar constituents encountered before, thus expectations are kindled. This corresponds to the highlighting of empty slots in the selected schema, and these expectations are compared with the actually encountered input. Depending on the outcome of this consumption analysis different next steps like search for further data or a reset, i.e. a new attempt employing another schema, are triggered. Monitoring of the whole process, and in particular of the flow of activation directed by the consumption analysis, yields valuable feedback for the optimum allocation of attention and resources including the selective establishment of useful new memory entries.
RFID Authentication, Efficient Proactive Information Security within Computational Security
Venue: arXiv cs.CR 2009
Year: 2009

We consider repeated communication sessions between a RFID Tag (e.g., Radio Frequency Identification, RFID Tag) and a RFID Verifier. A proactive information theoretic security scheme is proposed. The scheme is based on the assumption that the information exchanged during at least one of every n successive communication sessions is not exposed to an adversary. The Tag and the Verifier maintain a vector of n entries that is repeatedly refreshed by pairwise xoring entries, with a new vector of n entries that is randomly chosen by the Tag and sent to the Verifier as a part of each communication session. The general case in which the adversary does not listen in k > 0 sessions among any n successive communication sessions is also considered. A lower bound of n(k+1) for the number of random numbers used during any n successive communication sessions is proven. In other words, we prove that an algorithm must use at least n(k+1) new random numbers during any n successive communication sessions. Then a randomized scheme that uses only O(n log n) new random numbers is presented. A computational secure scheme which is based on the information theoretic secure scheme is used to ensure that even in the case that the adversary listens in all the information exchanges, the communication between the Tag and the Verifier is secure.
Learning for Dynamic subsumption
Venue: arXiv cs.AI 2009
Year: 2009

In this paper a new dynamic subsumption technique for Boolean CNF formulae is proposed. It exploits simple and sufficient conditions to detect during conflict analysis, clauses from the original formula that can be reduced by subsumption. During the learnt clause derivation, and at each step of the resolution process, we simply check for backward subsumption between the current resolvent and clauses from the original formula and encoded in the implication graph. Our approach give rise to a strong and dynamic simplification technique that exploits learning to eliminate literals from the original clauses. Experimental results show that the integration of our dynamic subsumption approach within the state-of-the-art SAT solvers Minisat and Rsat achieves interesting improvements particularly on crafted instances.
Deterministic Capacity of MIMO Relay Networks
Venue: arXiv cs.IT 2009
Year: 2009

The deterministic capacity of a relay network is the capacity of a network when relays are restricted to transmitting \emph{reliable} information, that is, (asymptotically) deterministic function of the source message. In this paper it is shown that the deterministic capacity of a number of MIMO relay networks can be found in the low power regime where $\SNR\to0$. This is accomplished through deriving single letter upper bounds and finding the limit of these as $\SNR\to0$. The advantage of this technique is that it overcomes the difficulty of finding optimum distributions for mutual information.
Safe Reasoning Over Ontologies
Venue: arXiv cs.AI 2009
Year: 2009

As ontologies proliferate and automatic reasoners become more powerful, the problem of protecting sensitive information becomes more serious. In particular, as facts can be inferred from other facts, it becomes increasingly likely that information included in an ontology, while not itself deemed sensitive, may be able to be used to infer other sensitive information. We first consider the problem of testing an ontology for safeness defined as its not being able to be used to derive any sensitive facts using a given collection of inference rules. We then consider the problem of optimizing an ontology based on the criterion of making as much useful information as possible available without revealing any sensitive facts.