OpenRaiser/Intern-Atlas huggingface dataset:
Comparator Circuits over Finite Bounded Posets
Venue: arXiv cs.CC 2017
Year: 2017

Comparator circuit model was originally introduced by Mayr and Subramanian (1992) (and further studied by Cook, Filmus and Le (2012)) to capture problems which are not known to be P-complete but still not known to admit efficient parallel algorithms. The class CC is the complexity class of problems many-one logspace reducible to the Comparator Circuit Value Problem and we know that NL is contained in CC which is inturn contained in P. Cook, Filmus and Le (2012) showed that CC is also the class of languages decided by polynomial size comparator circuits. We study generalizations of the comparator circuit model that work over fixed finite bounded posets. We observe that there are universal comparator circuits even over arbitrary fixed finite bounded posets. Building on this, we show that general (resp. skew) comparator circuits of polynomial size over fixed finite distributive lattices characterizes CC (resp. L). Complementing this, we show that general comparator circuits of polynomial size over arbitrary fixed finite lattices exactly characterizes P even when the comparator circuit is skew. In addition, we show a characterization of the class NP by a family of polynomial sized comparator circuits over fixed {\em finite bounded posets}. These results generalize the results by Cook, Filmus and Le (2012) regarding the power of comparator circuits. As an aside, we consider generalizations of Boolean formulae over arbitrary lattices. We show that Spira's theorem (1971) can be extended to this setting as well and show that polynomial sized Boolean formulae over finite fixed lattices capture exactly NC^1.
Competition and Efficiency of Coalitions in Cournot Games with Uncertainty
Venue: arXiv cs.GT 2017
Year: 2017

We investigate the impact of coalition formation on the efficiency of Cournot games where producers face uncertainties. In particular, we study a market model where firms must determine their output before an uncertain production capacity is realized. In contrast to standard Cournot models, we show that the game is not efficient when there are many small firms. Instead, producers tend to act conservatively to hedge against their risks. We show that in the presence of uncertainty, the game becomes efficient when firms are allowed to take advantage of diversity to form groups of certain sizes. We characterize the tradeoff between market power and uncertainty reduction as a function of group size. In particular, we compare the welfare and output obtained with coalitional competition, with the same benchmarks when output is controlled by a single system operator. We show when there are $N$ firms present, competition between groups of size $Ω(\sqrt{N})$ results in equilibria that are socially optimal in terms of welfare and groups of size $Ω(N^{2/3})$ are socially optimal in terms of production. We also extend our results to the case of uncertain demand by establishing an equivalency between Cournot oligopoly and Cournot Oligopsony. We demonstrate our results with real data from electricity markets with significant wind power penetration.
On the zone of a circle in an arrangement of lines
Venue: arXiv cs.CG 2017
Year: 2017

Let $\mathcal L$ be a set of $n$ lines in the plane, and let $C$ be a convex curve in the plane, like a circle or a parabola. The "zone" of $C$ in $\mathcal L$, denoted $\mathcal Z(C,\mathcal L)$, is defined as the set of all cells in the arrangement $\mathcal A(\mathcal L)$ that are intersected by $C$. Edelsbrunner et al. (1992) showed that the complexity (total number of edges or vertices) of $\mathcal Z(C,\mathcal L)$ is at most $O(nα(n))$, where $α$ is the inverse Ackermann function. They did this by translating the sequence of edges of $\mathcal Z(C,\mathcal L)$ into a sequence $S$ that avoids the subsequence $ababa$. Whether the worst-case complexity of $\mathcal Z(C,\mathcal L)$ is only linear is a longstanding open problem. Since the relaxation of the problem to pseudolines does have a $Θ(nα(n))$ bound, any proof of $O(n)$ for the case of straight lines must necessarily use geometric arguments. In this paper we present some such geometric arguments. We show that, if $C$ is a circle, then certain configurations of straight-line segments with endpoints on $C$ are impossible. In particular, we show that there exists a Hart-Sharir sequence that cannot appear as a subsequence of $S$. The Hart-Sharir sequences are essentially the only known way to construct $ababa$-free sequences of superlinear length. Hence, if it could be shown that every family of $ababa$-free sequences of superlinear-length eventually contains all Hart-Sharir sequences, it would follow that the complexity of $\mathcal Z(C,\mathcal L)$ is $O(n)$ whenever $C$ is a circle.
Hub Location under Uncertainty: a Minimax Regret Model for the Capacitated Problem with Multiple Allocations
Venue: arXiv cs.DS 2017
Year: 2017

In this paper the capacitated hub location problem is formulated by a minimax regret model, which takes into account uncertain setup cost and demand. We focus on hub location with multiple allocations as a strategic problem requiring one definite solution. Investigating how deterministic models may lead to sub-optimal solutions, we provide an efficient formulation method for the problem. A computational analysis is performed to investigate the impact of uncertainty on the location of hubs. The suggested model is also compared with an alternative method, seasonal optimization, in terms of efficiency and practicability. The results indicate the importance of incorporating stochasticity and variability of parameters in solving practical hub location problems. Applying our method to a case study derived from an industrial food production company, we solve a logistical problem involving seasonal demand and uncertainty. The solution yields a definite hub network configuration to be implemented throughout the planning horizon.
Distribution System Topology Detection Using Consumer Load and Line Flow Measurements
Venue: arXiv cs.SY 2017
Year: 2017

This work presents a topology detection method combining home smart meter information and sparse line flow measurements. The problem is formulated as a spanning tree detection problem over a graph given partial nodal and edge flow information in a deterministic and stochastic setting. In the deterministic case of known nodal power consumption and edge flows we provide sensor placement criterion which guarantees correct identification of all spanning trees. We then present a detection method which is polynomial in complexity to the size of the graph. In the stochastic case where loads are given by forecasts derived from delayed smart meter data, we provide a combinatorial Maximum a Posteriori (MAP) detector and a polynomial complexity approximate MAP detector which is shown to work near optimum in low noise regime numerical cases and moderately well in higher noise regime.
Predicting Complete 3D Models of Indoor Scenes
Venue: arXiv cs.CV 2017
Year: 2017

One major goal of vision is to infer physical models of objects, surfaces, and their layout from sensors. In this paper, we aim to interpret indoor scenes from one RGBD image. Our representation encodes the layout of walls, which must conform to a Manhattan structure but is otherwise flexible, and the layout and extent of objects, modeled with CAD-like 3D shapes. We represent both the visible and occluded portions of the scene, producing a complete 3D parse. Such a scene interpretation is useful for robotics and visual reasoning, but difficult to produce due to the well-known challenge of segmentation, the high degree of occlusion, and the diversity of objects in indoor scene. We take a data-driven approach, generating sets of potential object regions, matching to regions in training images, and transferring and aligning associated 3D models while encouraging fit to observations and overall consistency. We demonstrate encouraging results on the NYU v2 dataset and highlight a variety of interesting directions for future work.
Throughput and Delay Scaling of Content-Centric Ad Hoc and Heterogeneous Wireless Networks
Venue: arXiv cs.NI 2017
Year: 2017

We study the throughput and delay characteristics of wireless caching networks, where users are mainly interested in retrieving content stored in the network, rather than in maintaining source-destination communication. Nodes are assumed to be uniformly distributed in the network area. Each node has a limited-capacity content store, which it uses to cache contents. We propose an achievable caching and transmission scheme whereby requesters retrieve content from the caching point which is closest in Euclidean distance. We establish the throughput and delay scaling of the achievable scheme, and show that the throughput and delay performance are order-optimal within a class of schemes. We then solve the caching optimization problem, and evaluate the network performance for a Zipf content popularity distribution, letting the number of content types and the network size both go to infinity. Finally, we extend our analysis to heterogeneous wireless networks where, in addition to wireless nodes, there are a number of base stations uniformly distributed at random in the network area. We show that in order to achieve a better performance in a heterogeneous network in the order sense, the number of base stations needs to be greater than the ratio of the number of nodes to the number of content types. Furthermore, we show that the heterogeneous network does not yield performance advantages in the order sense if the Zipf content popularity distribution exponent exceeds 3/2.
Graph Bisection with Pareto-Optimization
Venue: arXiv cs.DS 2017
Year: 2017

We introduce FlowCutter, a novel algorithm to compute a set of edge cuts or node separators that optimize cut size and balance in the Pareto-sense. Our core algorithm solves the balanced connected st-edge-cut problem, where two given nodes s and t must be separated by removing edges to obtain two connected parts. Using the core algorithm we build variants that compute node separators and are independent of s and t. Using the Pareto-set we can identify cuts with a particularly good trade-off between cut size and balance that can be used to compute contraction and minimum fill-in orders, which can be used in Customizable Contraction Hierarchies (CCH), a speed-up technique for shortest path computations. Our core algorithm runs in O(cm) time where m is the number of edges and c the cut size. This makes it well-suited for large graphs with small cuts, such as road graphs, which are our primary application. For road graphs we present an extensive experimental study demonstrating that FlowCutter outperforms the current state of the art both in terms of cut sizes as well as CCH performance.
Linear Maximum Margin Classifier for Learning from Uncertain Data
Venue: arXiv cs.LG 2017
Year: 2017

In this paper, we propose a maximum margin classifier that deals with uncertainty in data input. More specifically, we reformulate the SVM framework such that each training example can be modeled by a multi-dimensional Gaussian distribution described by its mean vector and its covariance matrix -- the latter modeling the uncertainty. We address the classification problem and define a cost function that is the expected value of the classical SVM cost when data samples are drawn from the multi-dimensional Gaussian distributions that form the set of the training examples. Our formulation approximates the classical SVM formulation when the training examples are isotropic Gaussians with variance tending to zero. We arrive at a convex optimization problem, which we solve efficiently in the primal form using a stochastic gradient descent approach. The resulting classifier, which we name SVM with Gaussian Sample Uncertainty (SVM-GSU), is tested on synthetic data and five publicly available and popular datasets; namely, the MNIST, WDBC, DEAP, TV News Channel Commercial Detection, and TRECVID MED datasets. Experimental results verify the effectiveness of the proposed method.
Undecidability of Equality in the Free Locally Cartesian Closed Category (Extended version)
Venue: arXiv cs.LO 2017
Year: 2017

We show that a version of Martin-Löf type theory with an extensional identity type former I, a unit type N1 , Sigma-types, Pi-types, and a base type is a free category with families (supporting these type formers) both in a 1- and a 2-categorical sense. It follows that the underlying category of contexts is a free locally cartesian closed category in a 2-categorical sense because of a previously proved biequivalence. We show that equality in this category is undecidable by reducing it to the undecidability of convertibility in combinatory logic. Essentially the same construction also shows a slightly strengthened form of the result that equality in extensional Martin-Löf type theory with one universe is undecidable.
Efficient Approximation Algorithms for Multi-Antennae Largest Weight Data Retrieval
Venue: arXiv cs.DS 2017
Year: 2017

In a mobile network, wireless data broadcast over $m$ channels (frequencies) is a powerful means for distributed dissemination of data to clients who access the channels through multi-antennae equipped on their mobile devices. The $δ$-antennae largest weight data retrieval ($δ$ALWDR) problem is to compute a schedule for downloading a subset of data items that has a maximum total weight using $δ$ antennae in a given time interval. In this paper, we propose a ratio $1-\frac{1}{e}-ε$ approximation algorithm for the $δ$-antennae largest weight data retrieval ($δ$ALWDR) problem that has the same ratio as the known result but a significantly improved time complexity of $O(2^{\frac{1}ε}\frac{1}εm^{7}T^{3.5}L)$ from $O(ε^{3.5}m^{\frac{3.5}ε}T^{3.5}L)$ when $δ=1$ \cite{lu2014data}. To our knowledge, our algorithm represents the first ratio $1-\frac{1}{e}-ε$ approximation solution to $δ$ALWDR for the general case of arbitrary $δ$. To achieve this, we first give a ratio $1-\frac{1}{e}$ algorithm for the $γ$-separated $δ$ALWDR ($δ$A$γ$LWDR) with runtime $O(m^{7}T^{3.5}L)$, under the assumption that every data item appears at most once in each segment of $δ$A$γ$LWDR, for any input of maximum length $L$ on $m$ channels in $T$ time slots. Then, we show that we can retain the same ratio for $δ$A$γ$LWDR without this assumption at the cost of increased time complexity to $O(2^γm^{7}T^{3.5}L)$. This result immediately yields an approximation solution of same ratio and time complexity for $δ$ALWDR, presenting a significant improvement of the known time complexity of ratio $1-\frac{1}{e}-ε$ approximation to the problem.
Efficient Vertex-Label Distance Oracles for Planar Graphs
Venue: arXiv cs.DS 2017
Year: 2017

We consider distance queries in vertex-labeled planar graphs. For any fixed $0 < ε\leq 1/2$ we show how to preprocess a directed planar graph with vertex labels and arc lengths into a data structure that answers queries of the following form. Given a vertex $u$ and a label $λ$ return a $(1+ε)$-approximation of the distance from $u$ to its closest vertex with label $λ$. For a directed planar graph with $n$ vertices, such that the ratio of the largest to smallest arc length is bounded by $N$, the preprocessing time is $O(ε^{-2}n\lg^{3}{n}\lg(nN))$, the data structure size is $O(ε^{-1}n\lg{n}\lg(nN))$, and the query time is $O(\lg\lg{n}\lg\lg(nN) + ε^{-1})$. We also point out that a vertex label distance oracle for undirected planar graphs suggested in an earlier version of this paper is incorrect.
Multiuser I-MMSE
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, we generalize the fundamental relation between the derivative of the mutual information and the minimum mean squared error (MMSE) to multiuser setups. We prove that the derivative of the mutual information with respect to the signal to noise ratio (SNR) is equal to the MMSE plus a covariance induced due to the interference, quantified by a term with respect to the cross correlation of the multiuser input estimates, the channels and the precoding matrices. We also derive new relations for the gradient of the conditional and non-conditional mutual information with respect to the MMSE. Capitalizing on the new fundamental relations, we derive closed form expressions of the mutual information for the multiuser channels, particularly the two user multiple access Gaussian channel driven by binary phase shift keying (BPSK) to illustrate and shed light on methods to derive similar expressions for higher level constellations. We capitalize on the new unveiled relation to derive the multiuser MMSE and mutual information in the low-SNR regime.
Deep Neural Networks Regularization for Structured Output Prediction
Venue: arXiv cs.LG 2017
Year: 2017

A deep neural network model is a powerful framework for learning representations. Usually, it is used to learn the relation $x \to y$ by exploiting the regularities in the input $x$. In structured output prediction problems, $y$ is multi-dimensional and structural relations often exist between the dimensions. The motivation of this work is to learn the output dependencies that may lie in the output data in order to improve the prediction accuracy. Unfortunately, feedforward networks are unable to exploit the relations between the outputs. In order to overcome this issue, we propose in this paper a regularization scheme for training neural networks for these particular tasks using a multi-task framework. Our scheme aims at incorporating the learning of the output representation $y$ in the training process in an unsupervised fashion while learning the supervised mapping function $x \to y$. We evaluate our framework on a facial landmark detection problem which is a typical structured output task. We show over two public challenging datasets (LFPW and HELEN) that our regularization scheme improves the generalization of deep neural networks and accelerates their training. The use of unlabeled data and label-only data is also explored, showing an additional improvement of the results. We provide an opensource implementation (https://github.com/sbelharbi/structured-output-ae) of our framework.
Frugal Bribery in Voting
Venue: arXiv cs.AI 2017
Year: 2017

Bribery in elections is an important problem in computational social choice theory. However, bribery with money is often illegal in elections. Motivated by this, we introduce the notion of frugal bribery and formulate two new pertinent computational problems which we call Frugal-bribery and Frugal- $bribery to capture bribery without money in elections. In the proposed model, the briber is frugal in nature and this is captured by her inability to bribe votes of a certain kind, namely, non-vulnerable votes. In the Frugal-bribery problem, the goal is to make a certain candidate win the election by changing only vulnerable votes. In the Frugal-{dollar}bribery problem, the vulnerable votes have prices and the goal is to make a certain candidate win the election by changing only vulnerable votes, subject to a budget constraint of the briber. We further formulate two natural variants of the Frugal-{dollar}bribery problem namely Uniform-frugal-{dollar}bribery and Nonuniform-frugal-{dollar}bribery where the prices of the vulnerable votes are, respectively, all the same or different. We study the computational complexity of the above problems for unweighted and weighted elections for several commonly used voting rules. We observe that, even if we have only a small number of candidates, the problems are intractable for all voting rules studied here for weighted elections, with the sole exception of the Frugal-bribery problem for the plurality voting rule. In contrast, we have polynomial time algorithms for the Frugal-bribery problem for plurality, veto, k-approval, k-veto, and plurality with runoff voting rules for unweighted elections. However, the Frugal-{dollar}bribery problem is intractable for all the voting rules studied here barring the plurality and the veto voting rules for unweighted elections.
Power Decoding Reed--Solomon Codes Up to the Johnson Radius
Venue: arXiv cs.IT 2017
Year: 2017

Power decoding, or "decoding using virtual interleaving" is a technique for decoding Reed--Solomon codes up to the Sudan radius. Since the method's inception, it has been an open question if it is possible to use this approach to decode up to the Johnson radius -- the decoding radius of the Guruswami--Sudan algorithm. In this paper we show that this can be done by incorporating a notion of multiplicities. As the original Power decoding, the proposed algorithm is a one-pass algorithm: decoding follows immediately from solving a shift-register type equation, which we show can be done in quasi-linear time. It is a "partial bounded-distance decoding algorithm" since it will fail to return a codeword for a few error patterns within its decoding radius; we investigate its failure behaviour theoretically as well as give simulation results. This is an extended version where we also show how the method can be made faster using the re-encoding technique or a syndrome formulation.
A New Oscillating-Error Technique for Classifiers
Venue: arXiv cs.AI 2017
Year: 2017

This paper describes a new method for reducing the error in a classifier. It uses an error correction update that includes the very simple rule of either adding or subtracting the error adjustment, based on whether the variable value is currently larger or smaller than the desired value. While a traditional neuron would sum the inputs together and then apply a function to the total, this new method can change the function decision for each input value. This gives added flexibility to the convergence procedure, where through a series of transpositions, variables that are far away can continue towards the desired value, whereas variables that are originally much closer can oscillate from one side to the other. Tests show that the method can successfully classify some benchmark datasets. It can also work in a batch mode, with reduced training times and can be used as part of a neural network architecture. Some comparisons with an earlier wave shape paper are also made.
Product-Mix Auctions and Tropical Geometry
Venue: arXiv cs.GT 2017
Year: 2017

In a recent and ongoing work, Baldwin and Klemperer explored a connection between tropical geometry and economics. They gave a sufficient condition for the existence of competitive equilibrium in product-mix auctions of indivisible goods. This result, which we call the Unimodularity Theorem, can also be traced back to the work of Danilov, Koshevoy, and Murota in discrete convex analysis. We give a new proof of the Unimodularity Theorem via the classical unimodularity theorem in integer programming. We give a unified treatment of these results via tropical geometry and formulate a new sufficient condition for competitive equilibrium when there are only two types of product. Generalizations of our theorem in higher dimensions are equivalent to various forms of the Oda conjecture in algebraic geometry.