OpenRaiser/Intern-Atlas huggingface dataset:
On Constant-Round Concurrent Zero-Knowledge from a Knowledge Assumption
Venue: arXiv cs.CR 2012
Year: 2012

In this work, we consider the long-standing open question of constructing constant-round concurrent zero-knowledge protocols in the plain model. Resolving this question is known to require non-black-box techniques. We consider non-black-box techniques for zero-knowledge based on knowledge assumptions, a line of thinking initiated by the work of Hada and Tanaka (CRYPTO 1998). Prior to our work, it was not known whether knowledge assumptions could be used for achieving security in the concurrent setting, due to a number of significant limitations that we discuss here. Nevertheless, we obtain the following results: 1. We obtain the first constant round concurrent zero-knowledge argument for \textbf{NP} in the plain model based on a new variant of knowledge of exponent assumption. Furthermore, our construction avoids the inefficiency inherent in previous non-black-box techniques such that those of Barak (FOCS 2001); we obtain our result through an efficient protocol compiler. 2. Unlike Hada and Tanaka, we do not require a knowledge assumption to argue the soundness of our protocol. Instead, we use a discrete log like assumption, which we call Diffie-Hellman Logarithm Assumption, to prove the soundness of our protocol. 3. We give evidence that our new variant of knowledge of exponent assumption is in fact plausible. In particular, we show that our assumption holds in the generic group model. 4. Knowledge assumptions are especially delicate assumptions whose plausibility may be hard to gauge. We give a novel framework to express knowledge assumptions in a more flexible way, which may allow for formulation of plausible assumptions and exploration of their impact and application in cryptography.
Adaptive Priority-Based Downlink Scheduling for WiMAX Networks
Venue: arXiv cs.NI 2012
Year: 2012

Supporting quality of service (QoS) guarantees for diverse multimedia services are the primary concerns for WiMAX (IEEE 802.16) networks. A scheduling scheme that satisfies QoS requirements has become more important for wireless communications. We propose a downlink scheduling scheme called adaptive priority-based downlink scheduling (APDS) for providing QoS guarantees in IEEE 802.16 networks. APDS comprises two major components: priority assignment and resource allocation. Different service-type connections primarily depend on their QoS requirements to adjust priority assignments and dispatch bandwidth resources dynamically. We consider both starvation avoidance and resource management. Simulation results show that our APDS methodology outperforms the representative scheduling approaches in QoS satisfaction and maintains fairness in starvation prevention.
Transceiver Design For SC-FDE Based MIMO Relay Systems
Venue: arXiv cs.IT 2012
Year: 2012

In this paper, we propose a joint transceiver design for single-carrier frequency-domain equalization (SC-FDE) based multiple-input multiple-output (MIMO) relay systems. To this end, we first derive the optimal minimum mean-squared error linear and decision-feedback frequency-domain equalization filters at the destination along with the corresponding error covariance matrices at the output of the equalizer. Subsequently, we formulate the source and relay precoding matrix design problem as the minimization of a family of Schur-convex and Schur-concave functions of the mean-squared errors at the output of the equalizer under separate power constraints for the source and the relay. By exploiting properties of the error covariance matrix and results from majorization theory, we derive the optimal structures of the source and relay precoding matrices, which allows us to transform the matrix optimization problem into a scalar power optimization problem. Adopting a high signal-to-noise ratio approximation for the objective function, we obtain the global optimal solution for the power allocation variables. Simulation results illustrate the excellent performance of the proposed system and its superiority compared to conventional orthogonal frequency-division multiplexing based MIMO relay systems.
Local optima networks and the performance of iterated local search
Venue: arXiv cs.AI 2012
Year: 2012

Local Optima Networks (LONs) have been recently proposed as an alternative model of combinatorial fitness landscapes. The model compresses the information given by the whole search space into a smaller mathematical object that is the graph having as vertices the local optima and as edges the possible weighted transitions between them. A new set of metrics can be derived from this model that capture the distribution and connectivity of the local optima in the underlying configuration space. This paper departs from the descriptive analysis of local optima networks, and actively studies the correlation between network features and the performance of a local search heuristic. The NK family of landscapes and the Iterated Local Search metaheuristic are considered. With a statistically-sound approach based on multiple linear regression, it is shown that some LONs' features strongly influence and can even partly predict the performance of a heuristic search algorithm. This study validates the expressive power of LONs as a model of combinatorial fitness landscapes.
Wireless Network-Coded Four-Way Relaying Using Latin Hyper-Cubes
Venue: arXiv cs.IT 2012
Year: 2012

This paper deals with physical layer network-coding for the four-way wireless relaying scenario where four nodes A, B, C and D wish to communicate their messages to all the other nodes with the help of the relay node R. The scheme given in the paper is based on the denoise-and-forward scheme proposed first by Popovski et al. Intending to minimize the number of channel uses, the protocol employs two phases: Multiple Access (MA) phase and Broadcast (BC) phase with each phase utilizing one channel use. This paper does the equivalent for the four-way relaying scenario as was done for the two-way relaying scenario by Koike-Akino et al., and for three-way relaying scenario in [3]. It is observed that adaptively changing the network coding map used at the relay according to the channel conditions greatly reduces the impact of multiple access interference which occurs at the relay during the MA phase. These network coding maps are so chosen so that they satisfy a requirement called exclusive law. We show that when the four users transmit points from the same M-PSK constellation, every such network coding map that satisfies the exclusive law can be represented by a 4-fold Latin Hyper-Cube of side M. The network code map used by the relay for the BC phase is explicitly obtained and is aimed at reducing the effect of interference at the MA stage.
The Perturbed Variation
Venue: arXiv cs.LG 2012
Year: 2012

We introduce a new discrepancy score between two distributions that gives an indication on their similarity. While much research has been done to determine if two samples come from exactly the same distribution, much less research considered the problem of determining if two finite samples come from similar distributions. The new score gives an intuitive interpretation of similarity; it optimally perturbs the distributions so that they best fit each other. The score is defined between distributions, and can be efficiently estimated from samples. We provide convergence bounds of the estimated score, and develop hypothesis testing procedures that test if two data sets come from similar distributions. The statistical power of this procedures is presented in simulations. We also compare the score's capacity to detect similarity with that of other known measures on real data.
The Swedish System of Innovation: Regional Synergies in a Knowledge-Based Economy
Venue: arXiv cs.CY 2012
Year: 2012

Based on the complete set of firm data for Sweden (N = 1,187,421; November 2011), we analyze the mutual information among the geographical, technological, and organizational distributions in terms of synergies at regional and national levels. Mutual information in three dimensions can become negative and thus indicate a net export of uncertainty by a system or, in other words, synergy in how knowledge functions are distributed over the carriers. Aggregation at the regional level (NUTS3) of the data organized at the municipal level (NUTS5) shows that 48.5% of the regional synergy is provided by the three metropolitan regions of Stockholm, Gothenburg, and Malmö/Lund. Sweden can be considered as a centralized and hierarchically organized system. Our results accord with other statistics, but this Triple Helix indicator measures synergy more specifically and quantitatively. The analysis also provides us with validation for using this measure in previous studies of more regionalized systems of innovation (such as Hungary and Norway).
Wireless Network Stability in the SINR Model
Venue: arXiv cs.NI 2012
Year: 2012

We study the stability of wireless networks under stochastic arrival processes of packets, and design efficient, distributed algorithms that achieve stability in the SINR (Signal to Interference and Noise Ratio) interference model. Specifically, we make the following contributions. We give a distributed algorithm that achieves $Ω(\frac{1}{\log^2 n})$-efficiency on all networks (where $n$ is the number of links in the network), for all length monotone, sub-linear power assignments. For the power control version of the problem, we give a distributed algorithm with $Ω(\frac{1}{\log n(\log n + \log \log Δ)})$-efficiency (where $Δ$ is the length diversity of the link set).
Dimensions and issues of mobile agent technology
Venue: arXiv cs.OH 2012
Year: 2012

Mobile Agent is a type of software system which acts "intelligently" on one's behalf with the feature of autonomy, learning ability and most importantly mobility. Now mobile agents are gaining interest in the research community. In this article mobile agents will be addressed as tools for mobile computing. Mobile agents have been used in applications ranging from network management to information management. We present mobile agent concept, characteristics, classification, need, applications and technical constraints in the mobile technology. We also provide a brief case study about how mobile agent is used for information retrieval.
A New Recursive Algorithm For Inverting A General Comrade Matrix
Venue: arXiv cs.SC 2012
Year: 2012

In this paper, the author present a reliable symbolic computational algorithm for inverting a general comrade matrix by using parallel computing along with recursion. The computational cost of our algorithm is O(n^2). The algorithm is implementable to the Computer Algebra System (CAS) such as MAPLE, MATLAB and MATHEMATICA. Three examples are presented for the sake of illustration.
A computational formulation for constrained solid and liquid membranes considering isogeometric finite elements
Venue: arXiv cs.CE 2012
Year: 2012

A geometrically exact membrane formulation is presented that is based on curvilinear coordinates and isogeometric finite elements, and is suitable for both solid and liquid membranes. The curvilinear coordinate system is used to describe both the theory and the finite element equations of the membrane. In the latter case this avoids the use of local cartesian coordinates at the element level. Consequently, no transformation of derivatives is required. The formulation considers a split of the in-plane and out-of-plane membrane contributions, which allows the construction of a stable formulation for liquid membranes with constant surface tension. The proposed membrane formulation is general, and accounts for dead and live loading, as well as enclosed volume, area, and contact constraints. The new formulation is illustrated by several challenging examples, considering linear and quadratic Lagrange elements, as well as isogeometric elements based on quadratic NURBS and cubic T-splines. It is seen that the isogeometric elements are much more accurate than standard Lagrange elements. The gain is especially large for the liquid membrane formulation since it depends explicitly on the surface curvature.
Basic Experiment Planning via Information Metrics: the RoboMendel Problem
Venue: arXiv cs.IT 2012
Year: 2012

In this paper we outline some mathematical questions that emerge from trying to "turn the scientific method into math". Specifically, we consider the problem of experiment planning (choosing the best experiment to do next) in explicit probabilistic and information theoretic terms. We formulate this as an information measurement problem; that is, we seek a rigorous definition of an information metric to measure the likely information yield of an experiment, such that maximizing the information metric will indeed reliably choose the best experiment to perform. We present the surprising result that defining the metric purely in terms of prediction power on observable variables yields a metric that can converge to the classical mutual information measuring how informative the experimental observation is about an underlying hidden variable. We show how the expectation potential information metric can compute the "information rate" of an experiment as well its total possible yield, and the information value of experimental controls. To illustrate the utility of these concepts for guiding fundamental scientific inquiry, we present an extensive case study (RoboMendel) applying these metrics to propose sequences of experiments for discovering the basic principles of genetics.
Designing Informative Securities
Venue: arXiv cs.GT 2012
Year: 2012

We create a formal framework for the design of informative securities in prediction markets. These securities allow a market organizer to infer the likelihood of events of interest as well as if he knew all of the traders' private signals. We consider the design of markets that are always informative, markets that are informative for a particular signal structure of the participants, and informative markets constructed from a restricted selection of securities. We find that to achieve informativeness, it can be necessary to allow participants to express information that may not be directly of interest to the market organizer, and that understanding the participants' signal structure is important for designing informative prediction markets.
Uncertain Congestion Games with Assorted Human Agent Populations
Venue: arXiv cs.GT 2012
Year: 2012

Congestion games model a wide variety of real-world resource congestion problems, such as selfish network routing, traffic route guidance in congested areas, taxi fleet optimization and crowd movement in busy areas. However, existing research in congestion games assumes: (a) deterministic movement of agents between resources; and (b) perfect rationality (i.e. maximizing their own expected value) of all agents. Such assumptions are not reasonable in dynamic domains where decision support has to be provided to humans. For instance, in optimizing the performance of a taxi fleet serving a city, movement of taxis can be involuntary or nondeterministic (decided by the specific customer who hires the taxi) and more importantly, taxi drivers may not follow advice provided by the decision support system (due to bounded rationality of humans). To that end, we contribute: (a) a general framework for representing congestion games under uncertainty for populations with assorted notions of rationality. (b) a scalable approach for solving the decision problem for perfectly rational agents which are in the mix with boundedly rational agents; and (c) a detailed evaluation on a synthetic and realworld data set to illustrate the usefulness of our new approach with respect to key social welfare metrics in the context of an assorted human-agent population. An interesting result from our experiments on a real-world taxi fleet optimization problem is that it is better (in terms of revenue and operational efficiency) for taxi drivers to follow perfectly rational strategies irrespective of the percentage of drivers not following the advice.
The Do-Calculus Revisited
Venue: arXiv cs.AI 2012
Year: 2012

The do-calculus was developed in 1995 to facilitate the identification of causal effects in non-parametric models. The completeness proofs of [Huang and Valtorta, 2006] and [Shpitser and Pearl, 2006] and the graphical criteria of [Tian and Shpitser, 2010] have laid this identification problem to rest. Recent explorations unveil the usefulness of the do-calculus in three additional areas: mediation analysis [Pearl, 2012], transportability [Pearl and Bareinboim, 2011] and metasynthesis. Meta-synthesis (freshly coined) is the task of fusing empirical results from several diverse studies, conducted on heterogeneous populations and under different conditions, so as to synthesize an estimate of a causal relation in some target environment, potentially different from those under study. The talk surveys these results with emphasis on the challenges posed by meta-synthesis. For background material, see http://bayes.cs.ucla.edu/csl_papers.html
Sample-efficient Nonstationary Policy Evaluation for Contextual Bandits
Venue: arXiv cs.LG 2012
Year: 2012

We present and prove properties of a new offline policy evaluator for an exploration learning setting which is superior to previous evaluators. In particular, it simultaneously and correctly incorporates techniques from importance weighting, doubly robust evaluation, and nonstationary policy evaluation approaches. In addition, our approach allows generating longer histories by careful control of a bias-variance tradeoff, and further decreases variance by incorporating information about randomness of the target policy. Empirical evidence from synthetic and realworld exploration learning problems shows the new evaluator successfully unifies previous approaches and uses information an order of magnitude more efficiently.
Dynamic Stochastic Orienteering Problems for Risk-Aware Applications
Venue: arXiv cs.AI 2012
Year: 2012

Orienteering problems (OPs) are a variant of the well-known prize-collecting traveling salesman problem, where the salesman needs to choose a subset of cities to visit within a given deadline. OPs and their extensions with stochastic travel times (SOPs) have been used to model vehicle routing problems and tourist trip design problems. However, they suffer from two limitations travel times between cities are assumed to be time independent and the route provided is independent of the risk preference (with respect to violating the deadline) of the user. To address these issues, we make the following contributions: We introduce (1) a dynamic SOP (DSOP) model, which is an extension of SOPs with dynamic (time-dependent) travel times; (2) a risk-sensitive criterion to allow for different risk preferences; and (3) a local search algorithm to solve DSOPs with this risk-sensitive criterion. We evaluated our algorithms on a real-world dataset for a theme park navigation problem as well as synthetic datasets employed in the literature.
A Theory of Goal-Oriented MDPs with Dead Ends
Venue: arXiv cs.AI 2012
Year: 2012

Stochastic Shortest Path (SSP) MDPs is a problem class widely studied in AI, especially in probabilistic planning. They describe a wide range of scenarios but make the restrictive assumption that the goal is reachable from any state, i.e., that dead-end states do not exist. Because of this, SSPs are unable to model various scenarios that may have catastrophic events (e.g., an airplane possibly crashing if it flies into a storm). Even though MDP algorithms have been used for solving problems with dead ends, a principled theory of SSP extensions that would allow dead ends, including theoretically sound algorithms for solving such MDPs, has been lacking. In this paper, we propose three new MDP classes that admit dead ends under increasingly weaker assumptions. We present Value Iteration-based as well as the more efficient heuristic search algorithms for optimally solving each class, and explore theoretical relationships between these classes. We also conduct a preliminary empirical study comparing the performance of our algorithms on different MDP classes, especially on scenarios with unavoidable dead ends.
A Spectral Algorithm for Latent Junction Trees
Venue: arXiv cs.LG 2012
Year: 2012

Latent variable models are an elegant framework for capturing rich probabilistic dependencies in many applications. However, current approaches typically parametrize these models using conditional probability tables, and learning relies predominantly on local search heuristics such as Expectation Maximization. Using tensor algebra, we propose an alternative parameterization of latent variable models (where the model structures are junction trees) that still allows for computation of marginals among observed variables. While this novel representation leads to a moderate increase in the number of parameters for junction trees of low treewidth, it lets us design a local-minimum-free algorithm for learning this parameterization. The main computation of the algorithm involves only tensor operations and SVDs which can be orders of magnitude faster than EM algorithms for large datasets. To our knowledge, this is the first provably consistent parameter learning technique for a large class of low-treewidth latent graphical models beyond trees. We demonstrate the advantages of our method on synthetic and real datasets.
Sparse Q-learning with Mirror Descent
Venue: arXiv cs.LG 2012
Year: 2012

This paper explores a new framework for reinforcement learning based on online convex optimization, in particular mirror descent and related algorithms. Mirror descent can be viewed as an enhanced gradient method, particularly suited to minimization of convex functions in highdimensional spaces. Unlike traditional gradient methods, mirror descent undertakes gradient updates of weights in both the dual space and primal space, which are linked together using a Legendre transform. Mirror descent can be viewed as a proximal algorithm where the distance generating function used is a Bregman divergence. A new class of proximal-gradient based temporal-difference (TD) methods are presented based on different Bregman divergences, which are more powerful than regular TD learning. Examples of Bregman divergences that are studied include p-norm functions, and Mahalanobis distance based on the covariance of sample gradients. A new family of sparse mirror-descent reinforcement learning methods are proposed, which are able to find sparse fixed points of an l1-regularized Bellman equation at significantly less computational cost than previous methods based on second-order matrix methods. An experimental study of mirror-descent reinforcement learning is presented using discrete and continuous Markov decision processes.
Bayesian Vote Manipulation: Optimal Strategies and Impact on Welfare
Venue: arXiv cs.GT 2012
Year: 2012

Most analyses of manipulation of voting schemes have adopted two assumptions that greatly diminish their practical import. First, it is usually assumed that the manipulators have full knowledge of the votes of the nonmanipulating agents. Second, analysis tends to focus on the probability of manipulation rather than its impact on the social choice objective (e.g., social welfare). We relax both of these assumptions by analyzing optimal Bayesian manipulation strategies when the manipulators have only partial probabilistic information about nonmanipulator votes, and assessing the expected loss in social welfare (in the broad sense of the term). We present a general optimization framework for the derivation of optimal manipulation strategies given arbitrary voting rules and distributions over preferences. We theoretically and empirically analyze the optimal manipulability of some popular voting rules using distributions and real data sets that go well beyond the common, but unrealistic, impartial culture assumption. We also shed light on the stark difference between the loss in social welfare and the probability of manipulation by showing that even when manipulation is likely, impact to social welfare is slight (and often negligible).