OpenRaiser/Intern-Atlas huggingface dataset:
Weak Singular Hybrid Automata
Venue: arXiv cs.FL 2014
Year: 2014

The framework of Hybrid automata, introduced by Alur, Courcourbetis, Henzinger, and Ho, provides a formal modeling and analysis environment to analyze the interaction between the discrete and the continuous parts of cyber-physical systems. Hybrid automata can be considered as generalizations of finite state automata augmented with a finite set of real-valued variables whose dynamics in each state is governed by a system of ordinary differential equations. Moreover, the discrete transitions of hybrid automata are guarded by constraints over the values of these real-valued variables, and enable discontinuous jumps in the evolution of these variables. Singular hybrid automata are a subclass of hybrid automata where dynamics is specified by state-dependent constant vectors. Henzinger, Kopke, Puri, and Varaiya showed that for even very restricted subclasses of singular hybrid automata, the fundamental verification questions, like reachability and schedulability, are undecidable. In this paper we present \emph{weak singular hybrid automata} (WSHA), a previously unexplored subclass of singular hybrid automata, and show the decidability (and the exact complexity) of various verification questions for this class including reachability (NP-Complete) and LTL model-checking (PSPACE-Complete). We further show that extending WSHA with a single unrestricted clock or extending WSHA with unrestricted variable updates lead to undecidability of reachability problem.
Sum Secrecy Rate in Full-Duplex Wiretap Channel with Imperfect CSI
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, we consider the achievable sum secrecy rate in full-duplex wiretap channel in the presence of an eavesdropper and imperfect channel state information (CSI). We assume that the users participating in full-duplex communication and the eavesdropper have single antenna each. The users have individual transmit power constraints. They also transmit jamming signals to improve the secrecy rates. We obtain the achievable perfect secrecy rate region by maximizing the sum secrecy rate. We also obtain the corresponding optimum powers of the message signals and the jamming signals. Numerical results that show the impact of imperfect CSI on the achievable secrecy rate region are presented.
Compressed Sensing for Energy-Efficient Wireless Telemonitoring: Challenges and Opportunities
Venue: arXiv cs.IT 2014
Year: 2014

As a lossy compression framework, compressed sensing has drawn much attention in wireless telemonitoring of biosignals due to its ability to reduce energy consumption and make possible the design of low-power devices. However, the non-sparseness of biosignals presents a major challenge to compressed sensing. This study proposes and evaluates a spatio-temporal sparse Bayesian learning algorithm, which has the desired ability to recover such non-sparse biosignals. It exploits both temporal correlation in each individual biosignal and inter-channel correlation among biosignals from different channels. The proposed algorithm was used for compressed sensing of multichannel electroencephalographic (EEG) signals for estimating vehicle drivers' drowsiness. Results showed that the drowsiness estimation was almost unaffected even if raw EEG signals (containing various artifacts) were compressed by 90%.
The power of linear programming for general-valued CSPs
Venue: arXiv cs.CC 2014
Year: 2014

Let $D$, called the domain, be a fixed finite set and let $Γ$, called the valued constraint language, be a fixed set of functions of the form $f:D^m\to\mathbb{Q}\cup\{\infty\}$, where different functions might have different arity $m$. We study the valued constraint satisfaction problem parametrised by $Γ$, denoted by VCSP$(Γ)$. These are minimisation problems given by $n$ variables and the objective function given by a sum of functions from $Γ$, each depending on a subset of the $n$ variables. Finite-valued constraint languages contain functions that take on only rational values and not infinite values. Our main result is a precise algebraic characterisation of valued constraint languages whose instances can be solved exactly by the basic linear programming relaxation (BLP). For a valued constraint language $Γ$, BLP is a decision procedure for $Γ$ if and only if $Γ$ admits a symmetric fractional polymorphism of every arity. For a finite-valued constraint language $Γ$, BLP is a decision procedure if and only if $Γ$ admits a symmetric fractional polymorphism of some arity, or equivalently, if $Γ$ admits a symmetric fractional polymorphism of arity 2. Using these results, we obtain tractability of several novel classes of problems, including problems over valued constraint languages that are: (1) submodular on arbitrary lattices; (2) $k$-submodular on arbitrary finite domains; (3) weakly (and hence strongly) tree-submodular on arbitrary trees.
Economic Efficiency Requires Interaction
Venue: arXiv cs.GT 2014
Year: 2014

We study the necessity of interaction between individuals for obtaining approximately efficient allocations. The role of interaction in markets has received significant attention in economic thinking, e.g. in Hayek's 1945 classic paper. We consider this problem in the framework of simultaneous communication complexity. We analyze the amount of simultaneous communication required for achieving an approximately efficient allocation. In particular, we consider two settings: combinatorial auctions with unit demand bidders (bipartite matching) and combinatorial auctions with subadditive bidders. For both settings we first show that non-interactive systems have enormous communication costs relative to interactive ones. On the other hand, we show that limited interaction enables us to find approximately efficient allocations.
Beating the Minimax Rate of Active Learning with Prior Knowledge
Venue: arXiv cs.LG 2014
Year: 2014

Active learning refers to the learning protocol where the learner is allowed to choose a subset of instances for labeling. Previous studies have shown that, compared with passive learning, active learning is able to reduce the label complexity exponentially if the data are linearly separable or satisfy the Tsybakov noise condition with parameter $κ=1$. In this paper, we propose a novel active learning algorithm using a convex surrogate loss, with the goal to broaden the cases for which active learning achieves an exponential improvement. We make use of a convex loss not only because it reduces the computational cost, but more importantly because it leads to a tight bound for the empirical process (i.e., the difference between the empirical estimation and the expectation) when the current solution is close to the optimal one. Under the assumption that the norm of the optimal classifier that minimizes the convex risk is available, our analysis shows that the introduction of the convex surrogate loss yields an exponential reduction in the label complexity even when the parameter $κ$ of the Tsybakov noise is larger than $1$. To the best of our knowledge, this is the first work that improves the minimax rate of active learning by utilizing certain priori knowledge.
PAPR Constrained Power Allocation for Iterative Frequency Domain Multiuser SIMO Detector
Venue: arXiv cs.IT 2014
Year: 2014

Peak to average power ratio (PAPR) constrained power allocation in single carrier multiuser (MU) single-input multiple-output (SIMO) systems with iterative frequency domain (FD) soft cancelation (SC) minimum mean squared error (MMSE) equalization is considered in this paper. To obtain full benefit of the iterative receiver, its convergence properties need to be taken into account also at the transmitter side. In this paper, we extend the existing results on the area of convergence constrained power allocation (CCPA) to consider the instantaneous PAPR at the transmit antenna of each user. In other words, we will introduce a constraint that PAPR cannot exceed a predetermined threshold. By adding the aforementioned constraint into the CCPA optimization framework, the power efficiency of a power amplifier (PA) can be significantly enhanced by enabling it to operate on its linear operation range. Hence, PAPR constraint is especially beneficial for power limited cell-edge users. In this paper, we will derive the instantaneous PAPR constraint as a function of transmit power allocation. Furthermore, successive convex approximation is derived for the PAPR constrained problem. Numerical results show that the proposed method can achieve the objectives described above.
Bayesian Discovery of Threat Networks
Venue: arXiv cs.SI 2014
Year: 2014

A novel unified Bayesian framework for network detection is developed, under which a detection algorithm is derived based on random walks on graphs. The algorithm detects threat networks using partial observations of their activity, and is proved to be optimum in the Neyman-Pearson sense. The algorithm is defined by a graph, at least one observation, and a diffusion model for threat. A link to well-known spectral detection methods is provided, and the equivalence of the random walk and harmonic solutions to the Bayesian formulation is proven. A general diffusion model is introduced that utilizes spatio-temporal relationships between vertices, and is used for a specific space-time formulation that leads to significant performance improvements on coordinated covert networks. This performance is demonstrated using a new hybrid mixed-membership blockmodel introduced to simulate random covert networks with realistic properties.
The Simplex Algorithm is NP-mighty
Venue: arXiv cs.DM 2014
Year: 2014

We propose to classify the power of algorithms by the complexity of the problems that they can be used to solve. Instead of restricting to the problem a particular algorithm was designed to solve explicitly, however, we include problems that, with polynomial overhead, can be solved 'implicitly' during the algorithm's execution. For example, we allow to solve a decision problem by suitably transforming the input, executing the algorithm, and observing whether a specific bit in its internal configuration ever switches during the execution. We show that the Simplex Method, the Network Simplex Method (both with Dantzig's original pivot rule), and the Successive Shortest Path Algorithm are NP-mighty, that is, each of these algorithms can be used to solve any problem in NP. This result casts a more favorable light on these algorithms' exponential worst-case running times. Furthermore, as a consequence of our approach, we obtain several novel hardness results. For example, for a given input to the Simplex Algorithm, deciding whether a given variable ever enters the basis during the algorithm's execution and determining the number of iterations needed are both NP-hard problems. Finally, we close a long-standing open problem in the area of network flows over time by showing that earliest arrival flows are NP-hard to obtain.
Optimal mechanisms with simple menus
Venue: arXiv cs.GT 2014
Year: 2014

We consider optimal mechanism design for the case with one buyer and two items. The buyer's valuations towards the two items are independent and additive. In this setting, optimal mechanism is unknown for general valuation distributions. We obtain two categories of structural results that shed light on the optimal mechanisms. The first category of results state that, under certain mild condition, the optimal mechanism has a monotone menu. In other words, in the menu that represents the optimal mechanism, as payment increases, the allocation probabilities for both items increase simultaneously. Applying this theorem, we derive a version of revenue monotonicity theorem that states stochastically superior distributions yield more revenue. Moreover, our theorem subsumes a previous result regarding sufficient conditions under which bundling is optimal. The second category of results state that, under certain conditions, the optimal mechanisms have few menu items. Our first result in this category says, for certain distributions, the optimal menu contains at most 4 items. The condition admits power (including uniform) density functions. Based on a similar proof of this result, we are able to obtain a wide class of distributions where bundling is optimal. Our second result in this category works for a weaker condition, under which the optimal menu contains at most 6 items. This condition includes exponential density functions. Our last result in this category works for unit-demand setting. It states that, for uniform distributions, the optimal menu contains at most 5 items. All these results are in sharp contrast to Hart and Nisan's recent result that finite-sized menu cannot guarantee any positive fraction of optimal revenue for correlated valuation distributions.
Local Similarities, Global Coding: An Algorithm for Feature Coding and its Applications
Venue: arXiv cs.CV 2014
Year: 2014

Data coding as a building block of several image processing algorithms has been received great attention recently. Indeed, the importance of the locality assumption in coding approaches is studied in numerous works and several methods are proposed based on this concept. We probe this assumption and claim that taking the similarity between a data point and a more global set of anchor points does not necessarily weaken the coding method as long as the underlying structure of the anchor points are taken into account. Based on this fact, we propose to capture this underlying structure by assuming a random walker over the anchor points. We show that our method is a fast approximate learning algorithm based on the diffusion map kernel. The experiments on various datasets show that making different state-of-the-art coding algorithms aware of this structure boosts them in different learning tasks.
Approximating Hereditary Discrepancy via Small Width Ellipsoids
Venue: arXiv cs.DS 2014
Year: 2014

The Discrepancy of a hypergraph is the minimum attainable value, over two-colorings of its vertices, of the maximum absolute imbalance of any hyperedge. The Hereditary Discrepancy of a hypergraph, defined as the maximum discrepancy of a restriction of the hypergraph to a subset of its vertices, is a measure of its complexity. Lovasz, Spencer and Vesztergombi (1986) related the natural extension of this quantity to matrices to rounding algorithms for linear programs, and gave a determinant based lower bound on the hereditary discrepancy. Matousek (2011) showed that this bound is tight up to a polylogarithmic factor, leaving open the question of actually computing this bound. Recent work by Nikolov, Talwar and Zhang (2013) showed a polynomial time $\tilde{O}(\log^3 n)$-approximation to hereditary discrepancy, as a by-product of their work in differential privacy. In this paper, we give a direct simple $O(\log^{3/2} n)$-approximation algorithm for this problem. We show that up to this approximation factor, the hereditary discrepancy of a matrix $A$ is characterized by the optimal value of simple geometric convex program that seeks to minimize the largest $\ell_{\infty}$ norm of any point in a ellipsoid containing the columns of $A$. This characterization promises to be a useful tool in discrepancy theory.
On the Expressiveness of TPTL and MTL over ω-Data Words
Venue: arXiv cs.LO 2014
Year: 2014

Metric Temporal Logic (MTL) and Timed Propositional Temporal Logic (TPTL) are prominent extensions of Linear Temporal Logic to specify properties about data languages. In this paper, we consider the class of data languages of non-monotonic data words over the natural numbers. We prove that, in this setting, TPTL is strictly more expressive than MTL. To this end, we introduce Ehrenfeucht-Fraisse (EF) games for MTL. Using EF games for MTL, we also prove that the MTL definability decision problem ("Given a TPTL-formula, is the language defined by this formula definable in MTL?") is undecidable. We also define EF games for TPTL, and we show the effect of various syntactic restrictions on the expressiveness of MTL and TPTL.
Auto-adaptative Laplacian Pyramids for High-dimensional Data Analysis
Venue: arXiv cs.AI 2014
Year: 2014

Non-linear dimensionality reduction techniques such as manifold learning algorithms have become a common way for processing and analyzing high-dimensional patterns that often have attached a target that corresponds to the value of an unknown function. Their application to new points consists in two steps: first, embedding the new data point into the low dimensional space and then, estimating the function value on the test point from its neighbors in the embedded space. However, finding the low dimension representation of a test point, while easy for simple but often not powerful enough procedures such as PCA, can be much more complicated for methods that rely on some kind of eigenanalysis, such as Spectral Clustering (SC) or Diffusion Maps (DM). Similarly, when a target function is to be evaluated, averaging methods like nearest neighbors may give unstable results if the function is noisy. Thus, the smoothing of the target function with respect to the intrinsic, low-dimensional representation that describes the geometric structure of the examined data is a challenging task. In this paper we propose Auto-adaptive Laplacian Pyramids (ALP), an extension of the standard Laplacian Pyramids model that incorporates a modified LOOCV procedure that avoids the large cost of the standard one and offers the following advantages: (i) it selects automatically the optimal function resolution (stopping time) adapted to the data and its noise, (ii) it is easy to apply as it does not require parameterization, (iii) it does not overfit the training set and (iv) it adds no extra cost compared to other classical interpolation methods. We illustrate numerically ALP's behavior on a synthetic problem and apply it to the computation of the DM projection of new patterns and to the extension to them of target function values on a radiation forecasting problem over very high dimensional patterns.
Choreography In Inter-Organizational Innovation Networks
Venue: arXiv cs.SI 2014
Year: 2014

This paper introduces the concept of choreography with respect to inter-organizational innovation networks, as they constitute an attractive environment to create innovation in different sectors. We argue that choreography governs behaviours by shaping the level of connectivity and cohesion among network members. It represents a valid organizational system able to sustain some activities and to reach effects generating innovation outcomes. This issue is tackled introducing a new framework in which we propose a network model as prerequisite for our hypothesis. The analysis is focused on inter-organizational innovation networks characterized by the presence of hubs, semi-peripheral and peripheral members lacking hierarchical authority. We sustain that the features of a network, bringing to synchronization phenomena, are extremely similar to those existing in innovation network characterized by the emergence of choreography. The effectiveness of our model is verified by providing a real case study that gives preliminary empirical hints on the network aptitude to perform choreography. Indeed, the innovation network analysed in the case study reveals characteristics causing synchronization and consequently the establishment of choreography.
Topology of the view complex
Venue: arXiv cs.DC 2014
Year: 2014

In this paper we consider a family of simplicial complexes, which we call the view complexes. Our choice of objects of study is motivated by theoretical distributed computing, since the view complex is a key simplicial construction used for protocol complexes in the snapshot computational model. We show that the view complex $\view$ can be collapsed to the well-known complex $χ(Δ^n)$, called standard chromatic subdivision of a simplex, and that $χ(Δ^n)$ is itself collapsible. Furthermore, we show that the collapses can be performed simultaneously in entire orbits of the natural symmetric group action. Our results yield a purely combinatorial and constructive understanding of the topology of view complexes, at the same time as they enhance our knowledge about the standard chromatic subdivision of a simplex.
Concurrent bisimulation algorithm
Venue: arXiv cs.LO 2014
Year: 2014

The coarsest bisimulation-finding problem plays an important role in the formal analysis of concurrent systems. For example, solving this problem allows the behavior of different processes to be compared or specifications to be verified. Hence, in this paper an efficient concurrent bisimulation algorithm is presented. It is based on the sequential Paige and Tarjan algorithm and the concept of the state signatures. The original solution follows Hopcroft's principle "process the smaller half". The presented algorithm uses its generalized version "process all but the largest one" better suited for concurrent and parallel applications. The running time achieved is comparable with the best known sequential and concurrent solutions. At the end of the work, the results of tests carried out are presented. The question of the lower bound for the running time of the optimal algorithm is also discussed.
On products and powers of linear codes under componentwise multiplication
Venue: arXiv cs.IT 2014
Year: 2014

In this text we develop the formalism of products and powers of linear codes under componentwise multiplication. As an expanded version of the author's talk at AGCT-14, focus is put mostly on basic properties and descriptive statements that could otherwise probably not fit in a regular research paper. On the other hand, more advanced results and applications are only quickly mentioned with references to the literature. We also point out a few open problems. Our presentation alternates between two points of view, which the theory intertwines in an essential way: that of combinatorial coding, and that of algebraic geometry. In appendices that can be read independently, we investigate topics in multilinear algebra over finite fields, notably we establish a criterion for a symmetric multilinear map to admit a symmetric algorithm, or equivalently, for a symmetric tensor to decompose as a sum of elementary symmetric tensors.
The Input/Output Complexity of Triangle Enumeration
Venue: arXiv cs.DS 2014
Year: 2014

We consider the well-known problem of enumerating all triangles of an undirected graph. Our focus is on determining the input/output (I/O) complexity of this problem. Let $E$ be the number of edges, $M<E$ the size of internal memory, and $B$ the block size. The best results obtained previously are sort$(E^{3/2})$ I/Os (Dementiev, PhD thesis 2006) and $O(E^2/(MB))$ I/Os (Hu et al., SIGMOD 2013), where sort$(n)$ denotes the number of I/Os for sorting $n$ items. We improve the I/O complexity to $O(E^{3/2}/(\sqrt{M} B))$ expected I/Os, which improves the previous bounds by a factor $\min(\sqrt{E/M},\sqrt{M})$. Our algorithm is cache-oblivious and also I/O optimal: We show that any algorithm enumerating $t$ distinct triangles must always use $Ω(t/(\sqrt{M} B))$ I/Os, and there are graphs for which $t=Ω(E^{3/2})$. Finally, we give a deterministic cache-aware algorithm using $O(E^{3/2}/(\sqrt{M} B))$ I/Os assuming $M\geq E^\varepsilon$ for a constant $\varepsilon > 0$. Our results are based on a new color coding technique, which may be of independent interest.