OpenRaiser/Intern-Atlas huggingface dataset:
Wheel Random Apollonian Graphs
Venue: arXiv cs.DM 2010
Year: 2010

In this paper a subset of High-Dimensional Random Apollonian networks, that we called Wheel Random Apollonian Graphs (WRAG), is considered. We show how to generate a Wheel Random Apollonian Graph from a wheel graph. We analyse some basic graph properties like vertices and edges cardinality, some question concerning cycles and the chromaticity in such type of graphs, we suggest further work on this type of graphs.
On Functional Decomposition of Multivariate Polynomials with Differentiation and Homogenization
Venue: arXiv cs.CR 2010
Year: 2010

In this paper, we give a theoretical analysis for the algorithms to compute functional decomposition for multivariate polynomials based on differentiation and homogenization which are proposed by Ye, Dai, Lam (1999) and Faug$μ$ere, Perret (2006, 2008, 2009). We show that a degree proper functional decomposition for a set of randomly decomposable quartic homogenous polynomials can be computed using the algorithm with high probability. This solves a conjecture proposed by Ye, Dai, and Lam (1999). We also propose a conjecture such that the decomposition for a set of polynomials can be computed from that of its homogenization with high probability. Finally, we prove that the right decomposition factors for a set of polynomials can be computed from its right decomposition factor space. Combining these results together, we prove that the algorithm can compute a degree proper decomposition for a set of randomly decomposable quartic polynomials with probability one when the base field is of characteristic zero, and with probability close to one when the base field is a finite field with sufficiently large number under the assumption that the conjeture is correct.
Secure Multiparty Computation with Partial Fairness
Venue: arXiv cs.CR 2010
Year: 2010

A protocol for computing a functionality is secure if an adversary in this protocol cannot cause more harm than in an ideal computation where parties give their inputs to a trusted party which returns the output of the functionality to all parties. In particular, in the ideal model such computation is fair -- all parties get the output. Cleve (STOC 1986) proved that, in general, fairness is not possible without an honest majority. To overcome this impossibility, Gordon and Katz (Eurocrypt 2010) suggested a relaxed definition -- 1/p-secure computation -- which guarantees partial fairness. For two parties, they construct 1/p-secure protocols for functionalities for which the size of either their domain or their range is polynomial (in the security parameter). Gordon and Katz ask whether their results can be extended to multiparty protocols. We study 1/p-secure protocols in the multiparty setting for general functionalities. Our main result is constructions of 1/p-secure protocols when the number of parties is constant provided that less than 2/3 of the parties are corrupt. Our protocols require that either (1) the functionality is deterministic and the size of the domain is polynomial (in the security parameter), or (2) the functionality can be randomized and the size of the range is polynomial. If the size of the domain is constant and the functionality is deterministic, then our protocol is efficient even when the number of parties is O(log log n) (where n is the security parameter). On the negative side, we show that when the number of parties is super-constant, 1/p-secure protocols are not possible when the size of the domain is polynomial.
Using the C4ISR Architecture Framework as a Tool to Facilitate VV&A for Simulation Systems within the Military Application Domain
Venue: arXiv cs.OH 2010
Year: 2010

To harmonize the individual architectures of the different commands, services, and agencies dealing with the development and procurement of Command, Control, Communications, Computing, Surveillance, Reconnaissance, and Intelligence (C4ISR) systems, the C4ISR Architecture Framework was developed based on existing and matured modeling techniques and methods. Within a short period, NATO adapted this method family as the NATO Consultation, Command, and Control (C3) System Architecture Framework to harmonize the efforts of the different nations. Based on these products, for every system to be fielded to be used in the US Armed Forces, a C4I Support Plan (C4ISP) has to be developed enabling the integration of the special system into the integrated C4I Architecture. The tool set proposed by these architecture frameworks connects operational views of the military user, system views of the developers, and the technical views for standards and integration methods needed to make the network centric system of systems work. The tools are therefore logically a valuable backbone for Verification, Validation, and Accreditation (VV&A). Their application is not limited to C4ISR systems; they can be used to define requirements and connected solutions and algorithms of Modeling and Simulation (M&S) systems as well. Especially for M&S systems to be used in connection with C4ISR system, the use of the C4ISR Architecture Framework would not only be a help, but can nearly be seen to be necessary to avoid double work and foster reuse and interoperability from the first stages of a project on. To enable the reader to build his own picture, the respective tools used and their application in the context of VV&A will be explained in form of an overview.
On Theorem 2.3 in "Prediction, Learning, and Games" by Cesa-Bianchi and Lugosi
Venue: arXiv cs.LG 2010
Year: 2010

The note presents a modified proof of a loss bound for the exponentially weighted average forecaster with time-varying potential. The regret term of the algorithm is upper-bounded by sqrt{n ln(N)} (uniformly in n), where N is the number of experts and n is the number of steps.
Mean Field Equilibrium in Dynamic Games with Complementarities
Venue: arXiv cs.GT 2010
Year: 2010

We study a class of stochastic dynamic games that exhibit strategic complementarities between players; formally, in the games we consider, the payoff of a player has increasing differences between her own state and the empirical distribution of the states of other players. Such games can be used to model a diverse set of applications, including network security models, recommender systems, and dynamic search in markets. Stochastic games are generally difficult to analyze, and these difficulties are only exacerbated when the number of players is large (as might be the case in the preceding examples). We consider an approximation methodology called mean field equilibrium to study these games. In such an equilibrium, each player reacts to only the long run average state of other players. We find necessary conditions for the existence of a mean field equilibrium in such games. Furthermore, as a simple consequence of this existence theorem, we obtain several natural monotonicity properties. We show that there exist a "largest" and a "smallest" equilibrium among all those where the equilibrium strategy used by a player is nondecreasing, and we also show that players converge to each of these equilibria via natural myopic learning dynamics; as we argue, these dynamics are more reasonable than the standard best response dynamics. We also provide sensitivity results, where we quantify how the equilibria of such games move in response to changes in parameters of the game (e.g., the introduction of incentives to players).
Quantifying and qualifying trust: Spectral decomposition of trust networks
Venue: arXiv cs.CR 2010
Year: 2010

In a previous FAST paper, I presented a quantitative model of the process of trust building, and showed that trust is accumulated like wealth: the rich get richer. This explained the pervasive phenomenon of adverse selection of trust certificates, as well as the fragility of trust networks in general. But a simple explanation does not always suggest a simple solution. It turns out that it is impossible to alter the fragile distribution of trust without sacrificing some of its fundamental functions. A solution for the vulnerability of trust must thus be sought elsewhere, without tampering with its distribution. This observation was the starting point of the present paper. It explores a different method for securing trust: not by redistributing it, but by mining for its sources. The method used to break privacy is thus also used to secure trust. A high level view of the mining methods that connect the two is provided in terms of *similarity networks*, and *spectral decomposition* of similarity preserving maps. This view may be of independent interest, as it uncovers a common conceptual and structural foundation of mathematical classification theory on one hand, and of the spectral methods of graph clustering and data mining on the other hand.
Static and Expanding Grid Coverage with Ant Robots : Complexity Results
Venue: arXiv cs.MA 2010
Year: 2010

In this paper we study the strengths and limitations of collaborative teams of simple agents. In particular, we discuss the efficient use of "ant robots" for covering a connected region on the Z^{2} grid, whose area is unknown in advance, and which expands at a given rate, where $n$ is the initial size of the connected region. We show that regardless of the algorithm used, and the robots' hardware and software specifications, the minimal number of robots required in order for such coverage to be possible is Ω({\sqrt{n}}). In addition, we show that when the region expands at a sufficiently slow rate, a team of Θ(\sqrt{n}) robots could cover it in at most O(n^{2} \ln n) time. This completion time can even be achieved by myopic robots, with no ability to directly communicate with each other, and where each robot is equipped with a memory of size O(1) bits w.r.t the size of the region (therefore, the robots cannot maintain maps of the terrain, nor plan complete paths). Regarding the coverage of non-expanding regions in the grid, we improve the current best known result of O(n^{2}) by demonstrating an algorithm that guarantees such a coverage with completion time of O(\frac{1}{k} n^{1.5} + n) in the worst case, and faster for shapes of perimeter length which is shorter than O(n).
On the Performance of Sparse Recovery via L_p-minimization (0<=p <=1)
Venue: arXiv cs.IT 2010
Year: 2010

It is known that a high-dimensional sparse vector x* in R^n can be recovered from low-dimensional measurements y= A^{m*n} x* (m<n) . In this paper, we investigate the recovering ability of l_p-minimization (0<=p<=1) as p varies, where l_p-minimization returns a vector with the least l_p ``norm'' among all the vectors x satisfying Ax=y. Besides analyzing the performance of strong recovery where l_p-minimization needs to recover all the sparse vectors up to certain sparsity, we also for the first time analyze the performance of ``weak'' recovery of l_p-minimization (0<=p<1) where the aim is to recover all the sparse vectors on one support with fixed sign pattern. When m/n goes to 1, we provide sharp thresholds of the sparsity ratio that differentiates the success and failure via l_p-minimization. For strong recovery, the threshold strictly decreases from 0.5 to 0.239 as p increases from 0 to 1. Surprisingly, for weak recovery, the threshold is 2/3 for all p in [0,1), while the threshold is 1 for l_1-minimization. We also explicitly demonstrate that l_p-minimization (p<1) can return a denser solution than l_1-minimization. For any m/n<1, we provide bounds of sparsity ratio for strong recovery and weak recovery respectively below which l_p-minimization succeeds with overwhelming probability. Our bound of strong recovery improves on the existing bounds when m/n is large. Regarding the recovery threshold, l_p-minimization has a higher threshold with smaller p for strong recovery; the threshold is the same for all p for sectional recovery; and l_1-minimization can outperform l_p-minimization for weak recovery. These are in contrast to traditional wisdom that l_p-minimization has better sparse recovery ability than l_1-minimization since it is closer to l_0-minimization. We provide an intuitive explanation to our findings and use numerical examples to illustrate the theoretical predictions.
On z-factorization and c-factorization of standard episturmian words
Venue: arXiv cs.DM 2010
Year: 2010

Ziv-Lempel and Crochemore factorization are two kinds of factorizations of words related to text processing. In this paper, we find these factorizations for standard epiesturmian words. Thus the previously known c-factorization of standard Sturmian words is provided as a special case. Moreover, the two factorizations are compared.
Prediction-based Adaptation (PRADA) Algorithm for Modulation and Coding
Venue: arXiv cs.IT 2010
Year: 2010

In this paper, we propose a novel adaptive modulation and coding (AMC) algorithm dedicated to reduce the feedback frequency of the channel state information (CSI). There have been already plenty of works on AMC so as to exploit the bandwidth more efficiently with the CSI feedback to the transmitter. However, in some occasions, frequent CSI feedback is not favorable in these systems. This work considers finite-state Markov chain (FSMC) based channel prediction to alleviate the feedback while maximizing the overall throughput. We derive the close-form of the frame error rate (FER) based on channel prediction using limited CSI feedback. In addition, instead of switching settings according to the CSI, we also provide means to combine both CSI and FER as the switching parameter. Numerical results illustrate that the average throughput of the proposed algorithm has significant performance improvement over fixed modulation and coding while the CSI feedback being largely reduced.
Single Carrier Architecture for High Data Rate Wireless PAN Communications System
Venue: arXiv cs.NI 2010
Year: 2010

A 60 GHz wireless Gigabit Ethernet (G.E.) communication system is developed at IETR. As the 60 GHz radio link operates only in a single-room configuration, an additional Radio over Fibre (RoF) link is used to ensure the communications in all the rooms of a residential environment. The realized system covers 2 GHz bandwidth. Due to the hardware constraints, a symbol rate at 875 Mbps is attained using simple single carrier architecture. In the baseband (BB) processing block, an original byte/frame synchronization process is designed to provide a smaller value of the preamble missing detection and false alarm probabilities. Bit error rate (BER) measurements have been realized in a large gym for line-of-sight (LOS) conditions. A Tx-Rx distance greater than 30 meters was attained with low BER using high gain antennas and forward error correction RS (255, 239) coding.
Distributed High Accuracy Peer-to-Peer Localization in Mobile Multipath Environments
Venue: arXiv cs.IT 2010
Year: 2010

In this paper we consider the problem of high accuracy localization of mobile nodes in a multipath-rich environment where sub-meter accuracies are required. We employ a peer to peer framework where the vehicles/nodes can get pairwise multipath-degraded ranging estimates in local neighborhoods together with a fixed number of anchor nodes. The challenge is to overcome the multipath-barrier with redundancy in order to provide the desired accuracies especially under severe multipath conditions when the fraction of received signals corrupted by multipath is dominating. We invoke a message passing analytical framework based on particle filtering and reveal its high accuracy localization promise through simulations.
Multimodal Biometric Systems - Study to Improve Accuracy and Performance
Venue: arXiv cs.AI 2010
Year: 2010

Biometrics is the science and technology of measuring and analyzing biological data of human body, extracting a feature set from the acquired data, and comparing this set against to the template set in the database. Experimental studies show that Unimodal biometric systems had many disadvantages regarding performance and accuracy. Multimodal biometric systems perform better than unimodal biometric systems and are popular even more complex also. We examine the accuracy and performance of multimodal biometric authentication systems using state of the art Commercial Off- The-Shelf (COTS) products. Here we discuss fingerprint and face biometric systems, decision and fusion techniques used in these systems. We also discuss their advantage over unimodal biometric systems.
Multiparty Symmetric Sum Types
Venue: arXiv cs.DC 2010
Year: 2010

This paper introduces a new theory of multiparty session types based on symmetric sum types, by which we can type non-deterministic orchestration choice behaviours. While the original branching type in session types can represent a choice made by a single participant and accepted by others determining how the session proceeds, the symmetric sum type represents a choice made by agreement among all the participants of a session. Such behaviour can be found in many practical systems, including collaborative workflow in healthcare systems for clinical practice guidelines (CPGs). Processes using the symmetric sums can be embedded into the original branching types using conductor processes. We show that this type-driven embedding preserves typability, satisfies semantic soundness and completeness, and meets the encodability criteria adapted to the typed setting. The theory leads to an efficient implementation of a prototypical tool for CPGs which automatically translates the original CPG specifications from a representation called the Process Matrix to symmetric sum types, type checks programs and executes them.
Precisely Analyzing Loss in Interface Adapter Chains
Venue: arXiv cs.SE 2010
Year: 2010

Interface adaptation allows code written for one interface to be used with a software component with another interface. When multiple adapters are chained together to make certain adaptations possible, we need a way to analyze how well the adaptation is done in case there are more than one chains that can be used. We introduce an approach to precisely analyzing the loss in an interface adapter chain using a simple form of abstract interpretation.
A near optimal algorithm for finding Euclidean shortest path in polygonal domain
Venue: arXiv cs.CG 2010
Year: 2010

We present an algorithm to find an {\it Euclidean Shortest Path} from a source vertex $s$ to a sink vertex $t$ in the presence of obstacles in $\Re^2$. Our algorithm takes $O(T+m(\lg{m})(\lg{n}))$ time and $O(n)$ space. Here, $O(T)$ is the time to triangulate the polygonal region, $m$ is the number of obstacles, and $n$ is the number of vertices. This bound is close to the known lower bound of $O(n+m\lg{m})$ time and $O(n)$ space. Our approach involve progressing shortest path wavefront as in continuous Dijkstra-type method, and confining its expansion to regions of interest.
Communication model of emuStudio emulation platform
Venue: arXiv cs.OH 2010
Year: 2010

Within the paper a description of communication model of plug-in based emuStudio emulation platform is given. The platform mentioned above allows the emulation of whole computer systems, configurable to the level of its components, represented by the plug-in modules of the platform. Development tasks still are in progress at the home institution of the authors. Currently the platform is exploited for teaching purposes within subjects aimed at machine-oriented languages and computer architectures. Versatility of the platform, given by its plug-in based architecture is a big advantage, when used as a teaching support tool. The paper briefly describes the emuStudio platform at its introductory part and then the mechanisms of inter-module communication are described.
Improved Algorithms for the Point-Set Embeddability problem for Plane 3-Trees
Venue: arXiv cs.CG 2010
Year: 2010

In the point set embeddability problem, we are given a plane graph $G$ with $n$ vertices and a point set $S$ with $n$ points. Now the goal is to answer the question whether there exists a straight-line drawing of $G$ such that each vertex is represented as a distinct point of $S$ as well as to provide an embedding if one does exist. Recently, in \cite{DBLP:conf/gd/NishatMR10}, a complete characterization for this problem on a special class of graphs known as the plane 3-trees was presented along with an efficient algorithm to solve the problem. In this paper, we use the same characterization to devise an improved algorithm for the same problem. Much of the efficiency we achieve comes from clever uses of the triangular range search technique. We also study a generalized version of the problem and present improved algorithms for this version of the problem as well.
Agnostic Learning of Monomials by Halfspaces is Hard
Venue: arXiv cs.CC 2010
Year: 2010

We prove the following strong hardness result for learning: Given a distribution of labeled examples from the hypercube such that there exists a monomial consistent with $(1-\eps)$ of the examples, it is NP-hard to find a halfspace that is correct on $(1/2+\eps)$ of the examples, for arbitrary constants $\eps > 0$. In learning theory terms, weak agnostic learning of monomials is hard, even if one is allowed to output a hypothesis from the much bigger concept class of halfspaces. This hardness result subsumes a long line of previous results, including two recent hardness results for the proper learning of monomials and halfspaces. As an immediate corollary of our result we show that weak agnostic learning of decision lists is NP-hard. Our techniques are quite different from previous hardness proofs for learning. We define distributions on positive and negative examples for monomials whose first few moments match. We use the invariance principle to argue that regular halfspaces (all of whose coefficients have small absolute value relative to the total $\ell_2$ norm) cannot distinguish between distributions whose first few moments match. For highly non-regular subspaces, we use a structural lemma from recent work on fooling halfspaces to argue that they are ``junta-like'' and one can zero out all but the top few coefficients without affecting the performance of the halfspace. The top few coefficients form the natural list decoding of a halfspace in the context of dictatorship tests/Label Cover reductions. We note that unlike previous invariance principle based proofs which are only known to give Unique-Games hardness, we are able to reduce from a version of Label Cover problem that is known to be NP-hard. This has inspired follow-up work on bypassing the Unique Games conjecture in some optimal geometric inapproximability results.
Handling Confidential Data on the Untrusted Cloud: An Agent-based Approach
Venue: arXiv cs.CR 2010
Year: 2010

Cloud computing allows shared computer and storage facilities to be used by a multitude of clients. While cloud management is centralized, the information resides in the cloud and information sharing can be implemented via off-the-shelf techniques for multiuser databases. Users, however, are very diffident for not having full control over their sensitive data. Untrusted database-as-a-server techniques are neither readily extendable to the cloud environment nor easily understandable by non-technical users. To solve this problem, we present an approach where agents share reserved data in a secure manner by the use of simple grant-and-revoke permissions on shared data.
Using ASP with recent extensions for causal explanations
Venue: arXiv cs.AI 2010
Year: 2010

We examine the practicality for a user of using Answer Set Programming (ASP) for representing logical formalisms. We choose as an example a formalism aiming at capturing causal explanations from causal information. We provide an implementation, showing the naturalness and relative efficiency of this translation job. We are interested in the ease for writing an ASP program, in accordance with the claimed ``declarative'' aspect of ASP. Limitations of the earlier systems (poor data structure and difficulty in reusing pieces of programs) made that in practice, the ``declarative aspect'' was more theoretical than practical. We show how recent improvements in working ASP systems facilitate a lot the translation, even if a few improvements could still be useful.