OpenRaiser/Intern-Atlas huggingface dataset:
Tag-Cloud Drawing: Algorithms for Cloud Visualization
Venue: arXiv cs.DS 2007
Year: 2007

Tag clouds provide an aggregate of tag-usage statistics. They are typically sent as in-line HTML to browsers. However, display mechanisms suited for ordinary text are not ideal for tags, because font sizes may vary widely on a line. As well, the typical layout does not account for relationships that may be known between tags. This paper presents models and algorithms to improve the display of tag clouds that consist of in-line HTML, as well as algorithms that use nested tables to achieve a more general 2-dimensional layout in which tag relationships are considered. The first algorithms leverage prior work in typesetting and rectangle packing, whereas the second group of algorithms leverage prior work in Electronic Design Automation. Experiments show our algorithms can be efficiently implemented and perform well.
We cite as we communicate: A communication model for the citation process
Venue: arXiv cs.DL 2007
Year: 2007

Building on ideas from linguistics, psychology, and social sciences about the possible mechanisms of human decision-making, we propose a novel theoretical framework for the citation analysis. Given the existing trend to investigate citation statistics in the context of various forms of power and Zipfian laws, we show that the popular models of citation have poor predictive ability and can hardly provide for an adequate explanation of the observed behavior of the empirical data. An alternative model is then derived, using the apparatus of statistical mechanics. The model is applied to approximate the citation frequencies of scientific articles from two large collections, and it demonstrates a predictive potential much superior to the one of any of the citation models known to the authors from the literature. Some analytical properties of the developed model are discussed, and conclusions are drawn. Directions for future work are also given at the paper's end.
Rapid Almost-Complete Broadcasting in Faulty Networks
Venue: arXiv cs.DC 2007
Year: 2007

This paper studies the problem of broadcasting in synchronous point-to-point networks, where one initiator owns a piece of information that has to be transmitted to all other vertices as fast as possible. The model of fractional dynamic faults with threshold is considered: in every step either a fixed number $T$, or a fraction $α$, of sent messages can be lost depending on which quantity is larger. As the main result we show that in complete graphs and hypercubes it is possible to inform all but a constant number of vertices, exhibiting only a logarithmic slowdown, i.e. in time $O(D\log n)$ where $D$ is the diameter of the network and $n$ is the number of vertices. Moreover, for complete graphs under some additional conditions (sense of direction, or $α<0.55$) the remaining constant number of vertices can be informed in the same time, i.e. $O(\log n)$.
TCP throughput guarantee in the DiffServ Assured Forwarding service: what about the results?
Venue: arXiv cs.NI 2007
Year: 2007

Since the proposition of Quality of Service architectures by the IETF, the interaction between TCP and the QoS services has been intensively studied. This paper proposes to look forward to the results obtained in terms of TCP throughput guarantee in the DiffServ Assured Forwarding (DiffServ/AF) service and to present an overview of the different proposals to solve the problem. It has been demonstrated that the standardized IETF DiffServ conditioners such as the token bucket color marker and the time sliding window color maker were not good TCP traffic descriptors. Starting with this point, several propositions have been made and most of them presents new marking schemes in order to replace or improve the traditional token bucket color marker. The main problem is that TCP congestion control is not designed to work with the AF service. Indeed, both mechanisms are antagonists. TCP has the property to share in a fair manner the bottleneck bandwidth between flows while DiffServ network provides a level of service controllable and predictable. In this paper, we build a classification of all the propositions made during these last years and compare them. As a result, we will see that these conditioning schemes can be separated in three sets of action level and that the conditioning at the network edge level is the most accepted one. We conclude that the problem is still unsolved and that TCP, conditioned or not conditioned, remains inappropriate to the DiffServ/AF service.
How to Guarantee Secrecy for Cryptographic Protocols
Venue: arXiv cs.CR 2007
Year: 2007

In this paper we propose a general definition of secrecy for cryptographic protocols in the Dolev-Yao model. We give a sufficient condition ensuring secrecy for protocols where rules have encryption depth at most two, that is satisfied by almost all practical protocols. The only allowed primitives in the class of protocols we consider are pairing and encryption with atomic keys. Moreover, we describe an algorithm of practical interest which transforms a cryptographic protocol into a secure one from the point of view of secrecy, without changing its original goal with respect to secrecy of nonces and keys, provided the protocol satisfies some conditions. These conditions are not very restrictive and are satisfied for most practical protocols.
Constructive Conjugate Codes for Quantum Error Correction and Cryptography
Venue: arXiv cs.IT 2007
Year: 2007

A conjugate code pair is defined as a pair of linear codes either of which contains the dual of the other. A conjugate code pair represents the essential structure of the corresponding Calderbank-Shor-Steane (CSS) quantum error-correcting code. It is known that conjugate code pairs are applicable to quantum cryptography. In this work, a polynomial construction of conjugate code pairs is presented. The constructed pairs achieve the highest known achievable rate on additive channels, and are decodable with algorithms of polynomial complexity.
The finite tiling problem is undecidable in the hyperbolic plane
Venue: arXiv cs.CG 2007
Year: 2007

In this paper, we consider the finite tiling problem which was proved undecidable in the Euclidean plane by Jarkko Kari in 1994. Here, we prove that the same problem for the hyperbolic plane is also undecidable.
Interior Point Decoding for Linear Vector Channels
Venue: arXiv cs.IT 2008
Year: 2008

In this paper, a novel decoding algorithm for low-density parity-check (LDPC) codes based on convex optimization is presented. The decoding algorithm, called interior point decoding, is designed for linear vector channels. The linear vector channels include many practically important channels such as inter symbol interference channels and partial response channels. It is shown that the maximum likelihood decoding (MLD) rule for a linear vector channel can be relaxed to a convex optimization problem, which is called a relaxed MLD problem. The proposed decoding algorithm is based on a numerical optimization technique so called interior point method with barrier function. Approximate variations of the gradient descent and the Newton methods are used to solve the convex optimization problem. In a decoding process of the proposed algorithm, a search point always lies in the fundamental polytope defined based on a low-density parity-check matrix. Compared with a convectional joint message passing decoder, the proposed decoding algorithm achieves better BER performance with less complexity in the case of partial response channels in many cases.
On Undetected Error Probability of Binary Matrix Ensembles
Venue: arXiv cs.IT 2008
Year: 2008

In this paper, an analysis of the undetected error probability of ensembles of binary matrices is presented. The ensemble called the Bernoulli ensemble whose members are considered as matrices generated from i.i.d. Bernoulli source is mainly considered here. The main contributions of this work are (i) derivation of the error exponent of the average undetected error probability and (ii) closed form expressions for the variance of the undetected error probability. It is shown that the behavior of the exponent for a sparse ensemble is somewhat different from that for a dense ensemble. Furthermore, as a byproduct of the proof of the variance formula, simple covariance formula of the weight distribution is derived.
World-set Decompositions: Expressiveness and Efficient Algorithms
Venue: arXiv cs.DB 2008
Year: 2008

Uncertain information is commonplace in real-world data management scenarios. The ability to represent large sets of possible instances (worlds) while supporting efficient storage and processing is an important challenge in this context. The recent formalism of world-set decompositions (WSDs) provides a space-efficient representation for uncertain data that also supports scalable processing. WSDs are complete for finite world-sets in that they can represent any finite set of possible worlds. For possibly infinite world-sets, we show that a natural generalization of WSDs precisely captures the expressive power of c-tables. We then show that several important decision problems are efficiently solvable on WSDs while they are NP-hard on c-tables. Finally, we give a polynomial-time algorithm for factorizing WSDs, i.e. an efficient algorithm for minimizing such representations.
The Impact of Channel Feedback on Opportunistic Relay Selection for Hybrid-ARQ in Wireless Networks
Venue: arXiv cs.IT 2008
Year: 2008

This paper presents a decentralized relay selection protocol for a dense wireless network and describes channel feedback strategies that improve its performance. The proposed selection protocol supports hybrid automatic-repeat-request transmission where relays forward parity information to the destination in the event of a decoding error. Channel feedback is employed for refining the relay selection process and for selecting an appropriate transmission mode in a proposed adaptive modulation transmission framework. An approximation of the throughput of the proposed adaptive modulation strategy is presented, and the dependence of the throughput on system parameters such as the relay contention probability and the adaptive modulation switching point is illustrated via maximization of this approximation. Simulations show that the throughput of the proposed selection strategy is comparable to that yielded by a centralized selection approach that relies on geographic information.
Order-Invariant MSO is Stronger than Counting MSO in the Finite
Venue: arXiv cs.LO 2008
Year: 2008

We compare the expressiveness of two extensions of monadic second-order logic (MSO) over the class of finite structures. The first, counting monadic second-order logic (CMSO), extends MSO with first-order modulo-counting quantifiers, allowing the expression of queries like ``the number of elements in the structure is even''. The second extension allows the use of an additional binary predicate, not contained in the signature of the queried structure, that must be interpreted as an arbitrary linear order on its universe, obtaining order-invariant MSO. While it is straightforward that every CMSO formula can be translated into an equivalent order-invariant MSO formula, the converse had not yet been settled. Courcelle showed that for restricted classes of structures both order-invariant MSO and CMSO are equally expressive, but conjectured that, in general, order-invariant MSO is stronger than CMSO. We affirm this conjecture by presenting a class of structures that is order-invariantly definable in MSO but not definable in CMSO.
A Normalizing Intuitionistic Set Theory with Inaccessible Sets
Venue: arXiv cs.LO 2008
Year: 2008

We propose a set theory strong enough to interpret powerful type theories underlying proof assistants such as LEGO and also possibly Coq, which at the same time enables program extraction from its constructive proofs. For this purpose, we axiomatize an impredicative constructive version of Zermelo-Fraenkel set theory IZF with Replacement and $ω$-many inaccessibles, which we call \izfio. Our axiomatization utilizes set terms, an inductive definition of inaccessible sets and the mutually recursive nature of equality and membership relations. It allows us to define a weakly-normalizing typed lambda calculus corresponding to proofs in \izfio according to the Curry-Howard isomorphism principle. We use realizability to prove the normalization theorem, which provides a basis for program extraction capability.
Geometric Complexity Theory VIII: On canonical bases for the nonstandard quantum groups
Venue: arXiv cs.CC 2008
Year: 2008

This article gives conjecturally correct algorithms to construct canonical bases of the irreducible polynomial representations and the matrix coordinate rings of the nonstandard quantum groups in GCT4 and GCT7, and canonical bases of the dually paired nonstandard deformations of the symmetric group algebra therein. These are generalizations of the canonical bases of the irreducible polynomial representations and the matrix coordinate ring of the standard quantum group, as constructed by Kashiwara and Lusztig, and the Kazhdan-Lusztig basis of the Hecke algebra. A positive ($#P$-) formula for the well-known plethysm constants follows from their conjectural properties and the duality and reciprocity conjectures in \cite{GCT7}.
Model and Program Repair via SAT Solving
Venue: arXiv cs.LO 2008
Year: 2008

We consider the following \emph{model repair problem}: given a finite Kripke structure $M$ and a specification formula $η$ in some modal or temporal logic, determine if $M$ contains a substructure $M'$ (with the same initial state) that satisfies $η$. Thus, $M$ can be ``repaired'' to satisfy the specification $η$ by deleting some transitions. We map an instance $(M, η)$ of model repair to a boolean formula $\repfor(M,η)$ such that $(M, η)$ has a solution iff $\repfor(M,η)$ is satisfiable. Furthermore, a satisfying assignment determines which transitions must be removed from $M$ to generate a model $M'$ of $η$. Thus, we can use any SAT solver to repair Kripke structures. Furthermore, using a complete SAT solver yields a complete algorithm: it always finds a repair if one exists. We extend our method to repair finite-state shared memory concurrent programs, to solve the discrete event supervisory control problem \cite{RW87,RW89}, to check for the existence of symmettric solutions \cite{ES93}, and to accomodate any boolean constraint on the existence of states and transitions in the repaired model. Finally, we show that model repair is NP-complete for CTL, and logics with polynomial model checking algorithms to which CTL can be reduced in polynomial time. A notable example of such a logic is Alternating-Time Temporal Logic (ATL).
Improving the LP bound of a MILP by branching concurrently
Venue: arXiv cs.DM 2008
Year: 2008

We'll measure the differences of the dual variables and the gain of the objective function when creating new problems, which each has one inequality more than the starting LP-instance. These differences of the dual variables are naturally connected to the branches. Then we'll choose those differences of dual variables, so that for all combinations of choices at the connected branches, all dual inequalities will hold for sure. By adding the gain of each chosen branching, we get a total gain, which gives a better limit of the original problem. By this technique it is also possible to create cuts.
Achieving the Gaussian Rate-Distortion Function by Prediction
Venue: arXiv cs.IT 2008
Year: 2008

The "water-filling" solution for the quadratic rate-distortion function of a stationary Gaussian source is given in terms of its power spectrum. This formula naturally lends itself to a frequency domain "test-channel" realization. We provide an alternative time-domain realization for the rate-distortion function, based on linear prediction. This solution has some interesting implications, including the optimality at all distortion levels of pre/post filtered vector-quantized differential pulse code modulation (DPCM), and a duality relationship with decision-feedback equalization (DFE) for inter-symbol interference (ISI) channels.
Recognizing Members of the Tournament Equilibrium Set is NP-hard
Venue: arXiv cs.CC 2008
Year: 2008

A recurring theme in the mathematical social sciences is how to select the "most desirable" elements given a binary dominance relation on a set of alternatives. Schwartz's tournament equilibrium set (TEQ) ranks among the most intriguing, but also among the most enigmatic, tournament solutions that have been proposed so far in this context. Due to its unwieldy recursive definition, little is known about TEQ. In particular, its monotonicity remains an open problem up to date. Yet, if TEQ were to satisfy monotonicity, it would be a very attractive tournament solution concept refining both the Banks set and Dutta's minimal covering set. We show that the problem of deciding whether a given alternative is contained in TEQ is NP-hard.
Relay Subset Selection in Wireless Networks Using Partial Decode-and-Forward Transmission
Venue: arXiv cs.IT 2008
Year: 2008

This paper considers the problem of selecting a subset of nodes in a two-hop wireless network to act as relays in aiding the communication between the source-destination pair. Optimal relay subset selection with the objective of maximizing the overall throughput is a difficult problem that depends on multiple factors including node locations, queue lengths and power consumption. A partial decode-and-forward strategy is applied in this paper to improve the tractability of the relay selection problem and performance of the overall network. Note that the number of relays selected ultimately determines the performance of the network. This paper benchmarks this performance by determining the net diversity achieved using the relays selected and the partial decode-and-forward strategy. This framework is subsequently used to further transform relay selection into a simpler relay placement problem, and two proximity-based approximation algorithms are developed to determine the appropriate set of relays to be selected in the network. Other selection strategies such as random relay selection and a greedy algorithm that relies on channel state information are also presented. This paper concludes by showing that the proposed proximity-based relay selection strategies yield near-optimal expected rates for a small number of selected relays.
Efficient modularity optimization by multistep greedy algorithm and vertex mover refinement
Venue: arXiv cs.DS 2008
Year: 2008

Identifying strongly connected substructures in large networks provides insight into their coarse-grained organization. Several approaches based on the optimization of a quality function, e.g., the modularity, have been proposed. We present here a multistep extension of the greedy algorithm (MSG) that allows the merging of more than one pair of communities at each iteration step. The essential idea is to prevent the premature condensation into few large communities. Upon convergence of the MSG a simple refinement procedure called "vertex mover" (VM) is used for reassigning vertices to neighboring communities to improve the final modularity value. With an appropriate choice of the step width, the combined MSG-VM algorithm is able to find solutions of higher modularity than those reported previously. The multistep extension does not alter the scaling of computational cost of the greedy algorithm.
Evaluating the Utility of Anonymized Network Traces for Intrusion Detection
Venue: arXiv cs.CR 2008
Year: 2008

Anonymization is the process of removing or hiding sensitive information in logs. Anonymization allows organizations to share network logs while not exposing sensitive information. However, there is an inherent trade off between the amount of information revealed in the log and the usefulness of the log to the client (the utility of a log). There are many anonymization techniques, and there are many ways to anonymize a particular log (that is, which fields to anonymize and how). Different anonymization policies will result in logs with varying levels of utility for analysis. In this paper we explore the effect of different anonymization policies on logs. We provide an empirical analysis of the effect of varying anonymization policies by looking at the number of alerts generated by an Intrusion Detection System. This is the first work to thoroughly evaluate the effect of single field anonymization policies on a data set. Our main contributions are to determine a set of fields that have a large impact on the utility of a log.
Multi-group ML Decodable Collocated and Distributed Space Time Block Codes
Venue: arXiv cs.IT 2008
Year: 2008

In this paper, collocated and distributed space-time block codes (DSTBCs) which admit multi-group maximum likelihood (ML) decoding are studied. First the collocated case is considered and the problem of constructing space-time block codes (STBCs) which optimally tradeoff rate and ML decoding complexity is posed. Recently, sufficient conditions for multi-group ML decodability have been provided in the literature and codes meeting these sufficient conditions were called Clifford Unitary Weight (CUW) STBCs. An algebraic framework based on extended Clifford algebras is proposed to study CUW STBCs and using this framework, the optimal tradeoff between rate and ML decoding complexity of CUW STBCs is obtained for few specific cases. Code constructions meeting this tradeoff optimally are also provided. The paper then focuses on multi-group ML decodable DSTBCs for application in synchronous wireless relay networks and three constructions of four-group ML decodable DSTBCs are provided. Finally, the OFDM based Alamouti space-time coded scheme proposed by Li-Xia for a 2 relay asynchronous relay network is extended to a more general transmission scheme that can achieve full asynchronous cooperative diversity for arbitrary number of relays. It is then shown how differential encoding at the source can be combined with the proposed transmission scheme to arrive at a new transmission scheme that can achieve full cooperative diversity in asynchronous wireless relay networks with no channel information and also no timing error knowledge at the destination node. Four-group decodable DSTBCs applicable in the proposed OFDM based transmission scheme are also given.
Approximation Algorithms for the Highway Problem under the Coupon Model
Venue: arXiv cs.DS 2008
Year: 2008

When a store sells items to customers, the store wishes to determine the prices of the items to maximize its profit. Intuitively, if the store sells the items with low (resp. high) prices, the customers buy more (resp. less) items, which provides less profit to the store. So it would be hard for the store to decide the prices of items. Assume that the store has a set V of n items and there is a set E of m customers who wish to buy those items, and also assume that each item i \in V has the production cost d_i and each customer e_j \in E has the valuation v_j on the bundle e_j \subseteq V of items. When the store sells an item i \in V at the price r_i, the profit for the item i is p_i=r_i-d_i. The goal of the store is to decide the price of each item to maximize its total profit. In most of the previous works, the item pricing problem was considered under the assumption that p_i \geq 0 for each i \in V, however, Balcan, et al. [In Proc. of WINE, LNCS 4858, 2007] introduced the notion of loss-leader, and showed that the seller can get more total profit in the case that p_i < 0 is allowed than in the case that p_i < 0 is not allowed. In this paper, we consider the line and the cycle highway problem, and show approximation algorithms for the line and/or cycle highway problem for which the smallest valuation is s and the largest valuation is \ell or all valuations are identical.