OpenRaiser/Intern-Atlas huggingface dataset:
A Dual Polynomial for OR
Venue: arXiv cs.CC 2008
Year: 2008

We reprove that the approximate degree of the OR function on n bits is Omega(sqrt(n)). We consider a linear program which is feasible if and only if there is an approximate polynomial for a given function, and apply the duality theory. The duality theory says that the primal program has no solution if and only if its dual has a solution. Therefore one can prove the nonexistence of an approximate polynomial by exhibiting a dual solution, coined the dual polynomial. We construct such a polynomial.
Moore and more and symmetry
Venue: arXiv cs.MA 2008
Year: 2008

In any spatially discrete model of pedestrian motion which uses a regular lattice as basis, there is the question of how the symmetry between the different directions of motion can be restored as far as possible but with limited computational effort. This question is equivalent to the question ''How important is the orientation of the axis of discretization for the result of the simulation?'' An optimization in terms of symmetry can be combined with the implementation of higher and heterogeniously distributed walking speeds by representing different walking speeds via different amounts of cells an agent may move during one round. Therefore all different possible neighborhoods for speeds up to v = 10 (cells per round) will be examined for the amount of deviation from radial symmetry. Simple criteria will be stated which will allow find an optimal neighborhood for each speed. It will be shown that following these criteria even the best mixture of steps in Moore and von Neumann neighborhoods is unable to reproduce the optimal neighborhood for a speed as low as 4.
Permeability Analysis based on information granulation theory
Venue: arXiv cs.NE 2008
Year: 2008

This paper describes application of information granulation theory, on the analysis of "lugeon data". In this manner, using a combining of Self Organizing Map (SOM) and Neuro-Fuzzy Inference System (NFIS), crisp and fuzzy granules are obtained. Balancing of crisp granules and sub- fuzzy granules, within non fuzzy information (initial granulation), is rendered in open-close iteration. Using two criteria, "simplicity of rules "and "suitable adaptive threshold error level", stability of algorithm is guaranteed. In other part of paper, rough set theory (RST), to approximate analysis, has been employed >.Validation of the proposed methods, on the large data set of in-situ permeability in rock masses, in the Shivashan dam, Iran, has been highlighted. By the implementation of the proposed algorithm on the lugeon data set, was proved the suggested method, relating the approximate analysis on the permeability, could be applied.
On the Sum-Capacity of Degraded Gaussian Multiaccess Relay Channels
Venue: arXiv cs.IT 2008
Year: 2008

The sum-capacity is studied for a K-user degraded Gaussian multiaccess relay channel (MARC) where the multiaccess signal received at the destination from the K sources and relay is a degraded version of the signal received at the relay from all sources, given the transmit signal at the relay. An outer bound on the capacity region is developed using cutset bounds. An achievable rate region is obtained for the decode-and-forward (DF) strategy. It is shown that for every choice of input distribution, the rate regions for the inner (DF) and outer bounds are given by the intersection of two K-dimensional polymatroids, one resulting from the multiaccess link at the relay and the other from that at the destination. Although the inner and outer bound rate regions are not identical in general, for both cases, a classical result on the intersection of two polymatroids is used to show that the intersection belongs to either the set of active cases or inactive cases, where the two bounds on the K-user sum-rate are active or inactive, respectively. It is shown that DF achieves the capacity region for a class of degraded Gaussian MARCs in which the relay has a high SNR link to the destination relative to the multiaccess link from the sources to the relay. Otherwise, DF is shown to achieve the sum-capacity for an active class of degraded Gaussian MARCs for which the DF sum-rate is maximized by a polymatroid intersection belonging to the set of active cases. This class is shown to include the class of symmetric Gaussian MARCs where all users transmit at the same power.
Application of Rough Set Theory to Analysis of Hydrocyclone Operation
Venue: arXiv cs.AI 2008
Year: 2008

This paper describes application of rough set theory, on the analysis of hydrocyclone operation. In this manner, using Self Organizing Map (SOM) as preprocessing step, best crisp granules of data are obtained. Then, using a combining of SOM and rough set theory (RST)-called SORST-, the dominant rules on the information table, obtained from laboratory tests, are extracted. Based on these rules, an approximate estimation on decision attribute is fulfilled. Finally, a brief comparison of this method with the SOM-NFIS system (briefly SONFIS) is highlighted.
Irregular turbo code design for the binary erasure channel
Venue: arXiv cs.IT 2008
Year: 2008

In this paper, the design of irregular turbo codes for the binary erasure channel is investigated. An analytic expression of the erasure probability of punctured recursive systematic convolutional codes is derived. This exact expression will be used to track the density evolution of turbo codes over the erasure channel, that will allow for the design of capacity-approaching irregular turbo codes. Next, we propose a graph-optimal interleaver for irregular turbo codes. Simulation results for different coding rates is shown at the end.
Symmetry Breaking for Maximum Satisfiability
Venue: arXiv cs.AI 2008
Year: 2008

Symmetries are intrinsic to many combinatorial problems including Boolean Satisfiability (SAT) and Constraint Programming (CP). In SAT, the identification of symmetry breaking predicates (SBPs) is a well-known, often effective, technique for solving hard problems. The identification of SBPs in SAT has been the subject of significant improvements in recent years, resulting in more compact SBPs and more effective algorithms. The identification of SBPs has also been applied to pseudo-Boolean (PB) constraints, showing that symmetry breaking can also be an effective technique for PB constraints. This paper extends further the application of SBPs, and shows that SBPs can be identified and used in Maximum Satisfiability (MaxSAT), as well as in its most well-known variants, including partial MaxSAT, weighted MaxSAT and weighted partial MaxSAT. As with SAT and PB, symmetry breaking predicates for MaxSAT and variants are shown to be effective for a representative number of problem domains, allowing solving problem instances that current state of the art MaxSAT solvers could not otherwise solve.
Source Coding with Mismatched Distortion Measures
Venue: arXiv cs.IT 2008
Year: 2008

We consider the problem of lossy source coding with a mismatched distortion measure. That is, we investigate what distortion guarantees can be made with respect to distortion measure $\tildeρ$, for a source code designed such that it achieves distortion less than $D$ with respect to distortion measure $ρ$. We find a single-letter characterization of this mismatch distortion and study properties of this quantity. These results give insight into the robustness of lossy source coding with respect to modeling errors in the distortion measure. They also provide guidelines on how to choose a good tractable approximation of an intractable distortion measure.
Weak Affine Light Typing is complete with respect to Safe Recursion on Notation
Venue: arXiv cs.LO 2008
Year: 2008

Weak affine light typing (WALT) assigns light affine linear formulae as types to a subset of lambda-terms of System F. WALT is poly-time sound: if a lambda-term M has type in WALT, M can be evaluated with a polynomial cost in the dimension of the derivation that gives it a type. The evaluation proceeds under any strategy of a rewriting relation which is a mix of both call-by-name and call-by-value beta-reductions. WALT weakens, namely generalizes, the notion of "stratification of deductions", common to some Light Systems -- those logical systems, derived from Linear logic, to characterize the set of Polynomial functions -- . A weaker stratification allows to define a compositional embedding of Safe recursion on notation (SRN) into WALT. It turns out that the expressivity of WALT is strictly stronger than the one of the known Light Systems. The embedding passes through the representation of a subsystem of SRN. It is obtained by restricting the composition scheme of SRN to one that can only use its safe variables linearly. On one side, this suggests that SRN, in fact, can be redefined in terms of more primitive constructs. On the other, the embedding of SRN into WALT enjoys the two following remarkable aspects. Every datatype, required by the embedding, is represented from scratch, showing the strong structural proof-theoretical roots of WALT. Moreover, the embedding highlights a stratification structure of the normal and safe arguments, normally hidden inside the world of SRN-normal/safe variables: the less an argument is "polyomially impredicative", the deeper, in a formal, proof-theoretical sense, it is represented inside WALT. Finally, since WALT is SRN-complete it is also polynomial-time complete since SRN is.
Scalable Distributed Video-on-Demand: Theoretical Bounds and Practical Algorithms
Venue: arXiv cs.NI 2008
Year: 2008

We analyze a distributed system where n nodes called boxes store a large set of videos and collaborate to serve simultaneously n videos or less. We explore under which conditions such a system can be scalable while serving any sequence of demands. We model this problem through a combination of two algorithms: a video allocation algorithm and a connection scheduling algorithm. The latter plays against an adversary that incrementally proposes video requests.
Sarbanes-Oxley: What About all the Spreadsheets?
Venue: arXiv cs.SE 2008
Year: 2008

The Sarbanes-Oxley Act of 2002 has finally forced corporations to examine the validity of their spreadsheets. They are beginning to understand the spreadsheet error literature, including what it tells them about the need for comprehensive spreadsheet testing. However, controlling for fraud will require a completely new set of capabilities, and a great deal of new research will be needed to develop fraud control capabilities. This paper discusses the riskiness of spreadsheets, which can now be quantified to a considerable degree. It then discusses how to use control frameworks to reduce the dangers created by spreadsheets. It focuses especially on testing, which appears to be the most crucial element in spreadsheet controls.
The equations of the ideal latches
Venue: arXiv cs.GL 2008
Year: 2008

The latches are simple circuits with feedback from the digital electrical engineering. We have included in our work the C element of Muller, the RS latch, the clocked RS latch, the D latch and also circuits containing two interconnected latches: the edge triggered RS flip-flop, the D flip-flop, the JK flip-flop, the T flip-flop. The purpose of this study is to model with equations the previous circuits, considered to be ideal, i.e. non-inertial. The technique of analysis is the pseudoboolean differential calculus.
Optimum Binary Search Trees on the Hierarchical Memory Model
Venue: arXiv cs.DS 2008
Year: 2008

The Hierarchical Memory Model (HMM) of computation is similar to the standard Random Access Machine (RAM) model except that the HMM has a non-uniform memory organized in a hierarchy of levels numbered 1 through h. The cost of accessing a memory location increases with the level number, and accesses to memory locations belonging to the same level cost the same. Formally, the cost of a single access to the memory location at address a is given by m(a), where m: N -> N is the memory cost function, and the h distinct values of m model the different levels of the memory hierarchy. We study the problem of constructing and storing a binary search tree (BST) of minimum cost, over a set of keys, with probabilities for successful and unsuccessful searches, on the HMM with an arbitrary number of memory levels, and for the special case h=2. While the problem of constructing optimum binary search trees has been well studied for the standard RAM model, the additional parameter m for the HMM increases the combinatorial complexity of the problem. We present two dynamic programming algorithms to construct optimum BSTs bottom-up. These algorithms run efficiently under some natural assumptions about the memory hierarchy. We also give an efficient algorithm to construct a BST that is close to optimum, by modifying a well-known linear-time approximation algorithm for the RAM model. We conjecture that the problem of constructing an optimum BST for the HMM with an arbitrary memory cost function m is NP-complete.
Spacetime Meshing for Discontinuous Galerkin Methods
Venue: arXiv cs.CG 2008
Year: 2008

Spacetime discontinuous Galerkin (SDG) finite element methods are used to solve such PDEs involving space and time variables arising from wave propagation phenomena in important applications in science and engineering. To support an accurate and efficient solution procedure using SDG methods and to exploit the flexibility of these methods, we give a meshing algorithm to construct an unstructured simplicial spacetime mesh over an arbitrary simplicial space domain. Our algorithm is the first spacetime meshing algorithm suitable for efficient solution of nonlinear phenomena in anisotropic media using novel discontinuous Galerkin finite element methods for implicit solutions directly in spacetime. Given a triangulated d-dimensional Euclidean space domain M (a simplicial complex) and initial conditions of the underlying hyperbolic spacetime PDE, we construct an unstructured simplicial mesh of the (d+1)-dimensional spacetime domain M x [0,infinity). Our algorithm uses a near-optimal number of spacetime elements, each with bounded temporal aspect ratio for any finite prefix M x [0,T] of spacetime. Our algorithm is an advancing front procedure that constructs the spacetime mesh incrementally, an extension of the Tent Pitcher algorithm of Ungor and Sheffer (2000). In 2DxTime, our algorithm simultaneously adapts the size and shape of spacetime tetrahedra to a spacetime error indicator. We are able to incorporate more general front modification operations, such as edge flips and limited mesh smoothing. Our algorithm represents recent progress towards a meshing algorithm in 2DxTime to track moving domain boundaries and other singular surfaces such as shock fronts.
Towards algebraic methods for maximum entropy estimation
Venue: arXiv cs.IT 2008
Year: 2008

We show that various formulations (e.g., dual and Kullback-Csiszar iterations) of estimation of maximum entropy (ME) models can be transformed to solving systems of polynomial equations in several variables for which one can use celebrated Grobner bases methods. Posing of ME estimation as solving polynomial equations is possible, in the cases where feature functions (sufficient statistic) that provides the information about the underlying random variable in the form of expectations are integer valued.
Distributed Space-Time Block Codes for the MIMO Multiple Access Channel
Venue: arXiv cs.IT 2008
Year: 2008

In this work, the Multiple transmit antennas Multiple Access Channel is considered. A construction of a family of distributed space-time codes for this channel is proposed. No Channel Side Information at the transmitters is assumed and users are not allowed to cooperate together. It is shown that the proposed code achieves the Diversity Multiplexing Tradeoff of the channel. As an example, we consider the two-user MIMO-MAC channel. Simulation results show the significant gain offered by the new coding scheme compared to an orthogonal transmission scheme, e.g. time sharing.
Distributed Space Time Codes for the Amplify-and-Forward Multiple-Access Relay Channel
Venue: arXiv cs.IT 2008
Year: 2008

In this work, we present a construction of a family of space-time block codes for a Multi-Access Amplify-and- Forward Relay channel with two users and a single half-duplex relay. It is assumed that there is no Channel Side Information at the transmitters and that they are not allowed to cooperate together. Using the Diversity Multiplexing Tradeoff as a tool to evaluate the performance, we prove that the proposed scheme is optimal in some sense. Moreover, we provide numerical results which show that the new scheme outperforms the orthogonal transmission scheme, e. g. time sharing and offers a significant gain.
Computation of unirational fields
Venue: arXiv cs.SC 2008
Year: 2008

One of the main contributions which Volker Weispfenning made to mathematics is related to Groebner bases theory. In this paper we present an algorithm for computing all algebraic intermediate subfields in a separably generated unirational field extension (which in particular includes the zero characteristic case). One of the main tools is Groebner bases theory. Our algorithm also requires computing primitive elements and factoring over algebraic extensions. Moreover, the method can be extended to finitely generated K-algebras.
Computation of unirational fields (extended abstract)
Venue: arXiv cs.SC 2008
Year: 2008

In this paper we present an algorithm for computing all algebraic intermediate subfields in a separably generated unirational field extension (which in particular includes the zero characteristic case). One of the main tools is Groebner bases theory. Our algorithm also requires computing computing primitive elements and factoring over algebraic extensions. Moreover, the method can be extended to finitely generated K-algebras.
Information Acquisition and Exploitation in Multichannel Wireless Networks
Venue: arXiv cs.DS 2008
Year: 2008

A wireless system with multiple channels is considered, where each channel has several transmission states. A user learns about the instantaneous state of an available channel by transmitting a control packet in it. Since probing all channels consumes significant energy and time, a user needs to determine what and how much information it needs to acquire about the instantaneous states of the available channels so that it can maximize its transmission rate. This motivates the study of the trade-off between the cost of information acquisition and its value towards improving the transmission rate. A simple model is presented for studying this information acquisition and exploitation trade-off when the channels are multi-state, with different distributions and information acquisition costs. The objective is to maximize a utility function which depends on both the cost and value of information. Solution techniques are presented for computing near-optimal policies with succinct representation in polynomial time. These policies provably achieve at least a fixed constant factor of the optimal utility on any problem instance, and in addition, have natural characterizations. The techniques are based on exploiting the structure of the optimal policy, and use of Lagrangean relaxations which simplify the space of approximately optimal solutions.
Measure and integral with purely ordinal scales
Venue: arXiv cs.DM 2008
Year: 2008

We develop a purely ordinal model for aggregation functionals for lattice valued functions, comprising as special cases quantiles, the Ky Fan metric and the Sugeno integral. For modeling findings of psychological experiments like the reflection effect in decision behaviour under risk or uncertainty, we introduce reflection lattices. These are complete linear lattices endowed with an order reversing bijection like the reflection at 0 on the real interval $[-1,1]$. Mathematically we investigate the lattice of non-void intervals in a complete linear lattice, then the class of monotone interval-valued functions and their inner product.
The Choquet integral for the aggregation of interval scales in multicriteria decision making
Venue: arXiv cs.DM 2008
Year: 2008

This paper addresses the question of which models fit with information concerning the preferences of the decision maker over each attribute, and his preferences about aggregation of criteria (interacting criteria). We show that the conditions induced by these information plus some intuitive conditions lead to a unique possible aggregation operator: the Choquet integral.
Necessary and Sufficient Conditions on Sparsity Pattern Recovery
Venue: arXiv cs.IT 2008
Year: 2008

The problem of detecting the sparsity pattern of a k-sparse vector in R^n from m random noisy measurements is of interest in many areas such as system identification, denoising, pattern recognition, and compressed sensing. This paper addresses the scaling of the number of measurements m, with signal dimension n and sparsity-level nonzeros k, for asymptotically-reliable detection. We show a necessary condition for perfect recovery at any given SNR for all algorithms, regardless of complexity, is m = Omega(k log(n-k)) measurements. Conversely, it is shown that this scaling of Omega(k log(n-k)) measurements is sufficient for a remarkably simple ``maximum correlation'' estimator. Hence this scaling is optimal and does not require more sophisticated techniques such as lasso or matching pursuit. The constants for both the necessary and sufficient conditions are precisely defined in terms of the minimum-to-average ratio of the nonzero components and the SNR. The necessary condition improves upon previous results for maximum likelihood estimation. For lasso, it also provides a necessary condition at any SNR and for low SNR improves upon previous work. The sufficient condition provides the first asymptotically-reliable detection guarantee at finite SNR.
A Reliability-based Framework for Multi-path Routing Analysis in Mobile Ad-Hoc Networks
Venue: arXiv cs.NI 2008
Year: 2008

Unlike traditional routing procedures that, at the best, single out a unique route, multi-path routing protocols discover proactively several alternative routes. It has been recognized that multi-path routing can be more efficient than traditional one mainly for mobile ad hoc networks, where route failure events are frequent. Most studies in the area of multi-path routing focus on heuristic methods, and the performances of these strategies are commonly evaluated by numerical simulations. The need of a theoretical analysis motivates such a paper, which proposes to resort to the terminal-pair routing reliability as performance metric. This metric allows one to assess the performance gain due to the availability of route diversity. By resorting to graph theory, we propose an analytical framework to evaluate the tolerance of multi-path route discovery processes against route failures for mobile ad hoc networks. Moreover, we derive a useful bound to easily estimate the performance improvements achieved by multi-path routing with respect to any traditional routing protocol. Finally, numerical simulation results show the effectiveness of this performance analysis.
Schemes for Deterministic Polynomial Factoring
Venue: arXiv cs.CC 2008
Year: 2008

In this work we relate the deterministic complexity of factoring polynomials (over finite fields) to certain combinatorial objects we call m-schemes. We extend the known conditional deterministic subexponential time polynomial factoring algorithm for finite fields to get an underlying m-scheme. We demonstrate how the properties of m-schemes relate to improvements in the deterministic complexity of factoring polynomials over finite fields assuming the generalized Riemann Hypothesis (GRH). In particular, we give the first deterministic polynomial time algorithm (assuming GRH) to find a nontrivial factor of a polynomial of prime degree n where (n-1) is a smooth number.