OpenRaiser/Intern-Atlas huggingface dataset:
Towards Better Separation between Deterministic and Randomized Query Complexity
Venue: arXiv cs.CC 2015
Year: 2015

We show that there exists a Boolean function $F$ which observes the following separations among deterministic query complexity $(D(F))$, randomized zero error query complexity $(R_0(F))$ and randomized one-sided error query complexity $(R_1(F))$: $R_1(F) = \widetilde{O}(\sqrt{D(F)})$ and $R_0(F)=\widetilde{O}(D(F))^{3/4}$. This refutes the conjecture made by Saks and Wigderson that for any Boolean function $f$, $R_0(f)=Ω({D(f)})^{0.753..}$. This also shows widest separation between $R_1(f)$ and $D(f)$ for any Boolean function. The function $F$ was defined by G{ö}{ö}s, Pitassi and Watson who studied it for showing a separation between deterministic decision tree complexity and unambiguous non-deterministic decision tree complexity. Independently of us, Ambainis et al proved that different variants of the function $F$ certify optimal (quadratic) separation between $D(f)$ and $R_0(f)$, and polynomial separation between $R_0(f)$ and $R_1(f)$. Viewed as separation results, our results are subsumed by those of Ambainis et al. However, while the functions considerd in the work of Ambainis et al are different variants of $F$, we work with the original function $F$ itself.
The Jordan-Brouwer theorem for graphs
Venue: arXiv cs.DM 2015
Year: 2015

We prove a discrete Jordan-Brouwer-Schoenflies separation theorem telling that a (d-1)-sphere H embedded in a d-sphere G defines two different connected graphs A,B in G such a way that the intersection of A and B is H and the union is G and such that the complementary graphs A,B are both d-balls. The graph theoretic definitions are due to Evako: the unit sphere of a vertex x of a graph G=(V,E) is the graph generated by {y | (x,y) in E} Inductively, a finite simple graph is called contractible if there is a vertex x such that both its unit sphere S(x) as well as the graph generated by V-{x} are contractible. Inductively, still following Evako, a d-sphere is a finite simple graph for which every unit sphere is a (d-1)-sphere and such that removing a single vertex renders the graph contractible. A d-ball B is a contractible graph for which each unit sphere S(x) is either a (d-1)-sphere in which case x is called an interior point, or S(x) is a (d-1)-ball in which case x is called a boundary point and such that the set of boundary point vertices generates a (d-1)-sphere. These inductive definitions are based on the assumption that the empty graph is the unique (-1)-sphere and that the one-point graph K_1 is the unique 0-ball and that K_1 is contractible. The theorem needs the following notion of embedding: a sphere H is embedded in a graph G if it is a sub-graph of G and if any intersection with any finite set of mutually adjacent unit spheres is a sphere. A knot of co-dimension k in G is a (d-k)-sphere H embedded in a d-sphere G.
On the DoF region of the two-user Interference Channel with an Instantaneous Relay
Venue: arXiv cs.IT 2015
Year: 2015

This paper studies the Degrees of Freedom (DoF) of the two-user multi-antenna Gaussian interference channel with an {\em instantaneous relay}, or relay without delay, where the relay transmitted signal in channel use $t$ can depend on all received signals up to and including that at channel use $t$. It is assumed that the two transmitters and the two receivers have $M$ antennas, while the relay receives through $N$ antennas and transmits through $L$ antennas. An achievable DoF region is derived, for all possible values of $(M,N,L)$, based on a memoryless linear transmission strategy at the relay that aims to {\it neutralize} as much interference as possible at the receivers. The proposed scheme is shown to attain the largest sum DoF among all memoryless linear transmission strategies at the relay and to actually be optimal for certain values of $(M,N,L)$.
A New Approximate Min-Max Theorem with Applications in Cryptography
Venue: arXiv cs.CR 2015
Year: 2015

We propose a novel proof technique that can be applied to attack a broad class of problems in computational complexity, when switching the order of universal and existential quantifiers is helpful. Our approach combines the standard min-max theorem and convex approximation techniques, offering quantitative improvements over the standard way of using min-max theorems as well as more concise and elegant proofs.
Fairy Lights in Femtoseconds: Aerial and Volumetric Graphics Rendered by Focused Femtosecond Laser Combined with Computational Holographic Fields
Venue: arXiv cs.GR 2015
Year: 2015

We present a method of rendering aerial and volumetric graphics using femtosecond lasers. A high-intensity laser excites a physical matter to emit light at an arbitrary 3D position. Popular applications can then be explored especially since plasma induced by a femtosecond laser is safer than that generated by a nanosecond laser. There are two methods of rendering graphics with a femtosecond laser in air: Producing holograms using spatial light modulation technology, and scanning of a laser beam by a galvano mirror. The holograms and workspace of the system proposed here occupy a volume of up to 1 cm^3; however, this size is scalable depending on the optical devices and their setup. This paper provides details of the principles, system setup, and experimental evaluation, and discussions on scalability, design space, and applications of this system. We tested two laser sources: an adjustable (30-100 fs) laser which projects up to 1,000 pulses per second at energy up to 7 mJ per pulse, and a 269-fs laser which projects up to 200,000 pulses per second at an energy up to 50 uJ per pulse. We confirmed that the spatiotemporal resolution of volumetric displays, implemented with these laser sources, is 4,000 and 200,000 dots per second. Although we focus on laser-induced plasma in air, the discussion presented here is also applicable to other rendering principles such as fluorescence and microbubble in solid/liquid materials.
Linear Codes with Two or Three Weights From Quadratic Bent Functions
Venue: arXiv cs.IT 2015
Year: 2015

Linear codes with few weights have applications in secrete sharing, authentication codes, association schemes, and strongly regular graphs. In this paper, several classes of $p$-ary linear codes with two or three weights are constructed from quadratic Bent functions over the finite field $\gf_p$, where $p$ is an odd prime. They include some earlier linear codes as special cases. The weight distributions of these linear codes are also determined.
Detection and Analysis of Emotion From Speech Signals
Venue: arXiv cs.SD 2015
Year: 2015

Recognizing emotion from speech has become one the active research themes in speech processing and in applications based on human-computer interaction. This paper conducts an experimental study on recognizing emotions from human speech. The emotions considered for the experiments include neutral, anger, joy and sadness. The distinuishability of emotional features in speech were studied first followed by emotion classification performed on a custom dataset. The classification was performed for different classifiers. One of the main feature attribute considered in the prepared dataset was the peak-to-peak distance obtained from the graphical representation of the speech signals. After performing the classification tests on a dataset formed from 30 different subjects, it was found that for getting better accuracy, one should consider the data collected from one person rather than considering the data from a group of people.
Information and Energy Cooperation in OFDM Relaying: Protocols and Optimization
Venue: arXiv cs.IT 2015
Year: 2015

Integrating power transfer into wireless communications for supporting simultaneous wireless information and power transfer (SWIPT) is a promising technique in energy-constrained wireless networks. While most existing work on SWIPT focuses on capacity-energy characterization, the benefits of cooperative transmission for SWIPT are much less investigated. In this paper, we consider SWIPT in an orthogonal frequency-division multiplexing (OFDM) relaying system, where a source node transfers information and a fraction of power simultaneously to a relay node, and the relay node uses the harvested power from the source node to forward the source information to the destination. To support the simultaneous information and energy cooperation, we first propose a transmission protocol assuming that the direct link between the source and destination does not exist, namely power splitting (PS) relaying protocol, where the relay node splits the received signal power in the first hop into two separate parts, one for information decoding and the other for energy harvesting. Then, we consider the case that the direct link between the source and destination is available, and the transmission mode adaptation (TMA) protocol is proposed, where the transmission can be completed by cooperative mode and direct mode simultaneously (over different subcarriers). In direct mode, when the source transmits signal to the destination, the destination receives the signal as information and the relay node concurrently receives the signal for energy harvesting. Joint resource allocation problems are formulated to maximize the system throughput. By using the Lagrangian dual method, we develop efficient algorithms to solve the nonconvex optimization problems.
New Approach to translation of Isolated Units in English-Korean Machine Translation
Venue: arXiv cs.CL 2015
Year: 2015

It is the most effective way for quick translation of tremendous amount of explosively increasing science and technique information material to develop a practicable machine translation system and introduce it into translation practice. This essay treats problems arising from translation of isolated units on the basis of the practical materials and experiments obtained in the development and introduction of English-Korean machine translation system. In other words, this essay considers establishment of information for isolated units and their Korean equivalents and word order.
Fully Dynamic Matching in Bipartite Graphs
Venue: arXiv cs.DS 2015
Year: 2015

Maximum cardinality matching in bipartite graphs is an important and well-studied problem. The fully dynamic version, in which edges are inserted and deleted over time has also been the subject of much attention. Existing algorithms for dynamic matching (in general graphs) seem to fall into two groups: there are fast (mostly randomized) algorithms that do not achieve a better than 2-approximation, and there slow algorithms with $Ø(\sqrt{m})$ update time that achieve a better-than-2 approximation. Thus the obvious question is whether we can design an algorithm -- deterministic or randomized -- that achieves a tradeoff between these two: a $o(\sqrt{m})$ approximation and a better-than-2 approximation simultaneously. We answer this question in the affirmative for bipartite graphs. Our main result is a fully dynamic algorithm that maintains a $3/2 + \eps$ approximation in worst-case update time $O(m^{1/4}\eps^{/2.5})$. We also give stronger results for graphs whose arboricity is at most $\al$, achieving a $(1+ \eps)$ approximation in worst-case time $O(\al (\al + \log n))$ for constant $\eps$. When the arboricity is constant, this bound is $O(\log n)$ and when the arboricity is polylogarithmic the update time is also polylogarithmic. The most important technical developement is the use of an intermediate graph we call an edge degree constrained subgraph (EDCS). This graph places constraints on the sum of the degrees of the endpoints of each edge: upper bounds for matched edges and lower bounds for unmatched edges. The main technical content of our paper involves showing both how to maintain an EDCS dynamically and that and EDCS always contains a sufficiently large matching. We also make use of graph orientations to help bound the amount of work done during each update.
Scientific Discovery by Machine Intelligence: A New Avenue for Drug Research
Venue: arXiv cs.AI 2015
Year: 2015

The majority of big data is unstructured and of this majority the largest chunk is text. While data mining techniques are well developed and standardized for structured, numerical data, the realm of unstructured data is still largely unexplored. The general focus lies on information extraction, which attempts to retrieve known information from text. The Holy Grail, however is knowledge discovery, where machines are expected to unearth entirely new facts and relations that were not previously known by any human expert. Indeed, understanding the meaning of text is often considered as one of the main characteristics of human intelligence. The ultimate goal of semantic artificial intelligence is to devise software that can understand the meaning of free text, at least in the practical sense of providing new, actionable information condensed out of a body of documents. As a stepping stone on the road to this vision I will introduce a totally new approach to drug research, namely that of identifying relevant information by employing a self-organizing semantic engine to text mine large repositories of biomedical research papers, a technique pioneered by Merck with the InfoCodex software. I will describe the methodology and a first successful experiment for the discovery of new biomarkers and phenotypes for diabetes and obesity on the basis of PubMed abstracts, public clinical trials and Merck internal documents. The reported approach shows much promise and has potential to impact fundamentally pharmaceutical research as a way to shorten time-to-market of novel drugs, and for early recognition of dead ends.
Segmentation of Three-dimensional Images with Parametric Active Surfaces and Topology Changes
Venue: arXiv cs.CV 2015
Year: 2015

In this paper, we introduce a novel parametric method for segmentation of three-dimensional images. We consider a piecewise constant version of the Mumford-Shah and the Chan-Vese functionals and perform a region-based segmentation of 3D image data. An evolution law is derived from energy minimization problems which push the surfaces to the boundaries of 3D objects in the image. We propose a parametric scheme which describes the evolution of parametric surfaces. An efficient finite element scheme is proposed for a numerical approximation of the evolution equations. Since standard parametric methods cannot handle topology changes automatically, an efficient method is presented to detect, identify and perform changes in the topology of the surfaces. One main focus of this paper are the algorithmic details to handle topology changes like splitting and merging of surfaces and change of the genus of a surface. Different artificial images are studied to demonstrate the ability to detect the different types of topology changes. Finally, the parametric method is applied to segmentation of medical 3D images.
Complexity of a Tetris variant
Venue: arXiv cs.CC 2015
Year: 2015

In this paper we are going to solve an open problem about the game tetris. We are going to give the first results in the complexity of a variant of offline tetris introduced by Erik Demaine, Susan Hohenberger and David Liben Nowell in their paper "Tetris is hard, even to approximate". In this variant, that follows a model of movements introduced by John Brzustowsky, we can move and rotate a piece the number of times we want in the first row. But then, when we left the piece fall, we cannot move it or rotate it anymore. We are going to demonstrate that the problem of maximizing the number of cleared lines of this variant on a particular game board, is NP-hard by reducing the 3-partition problem to the problem of clearing the board in this variant of tetris
Convex Relaxations for Gas Expansion Planning
Venue: arXiv cs.CE 2015
Year: 2015

Expansion of natural gas networks is a critical process involving substantial capital expenditures with complex decision-support requirements. Given the non-convex nature of gas transmission constraints, global optimality and infeasibility guarantees can only be offered by global optimisation approaches. Unfortunately, state-of-the-art global optimisation solvers are unable to scale up to real-world size instances. In this study, we present a convex mixed-integer second-order cone relaxation for the gas expansion planning problem under steady-state conditions. The underlying model offers tight lower bounds with high computational efficiency. In addition, the optimal solution of the relaxation can often be used to derive high-quality solutions to the original problem, leading to provably tight optimality gaps and, in some cases, global optimal soluutions. The convex relaxation is based on a few key ideas, including the introduction of flux direction variables, exact McCormick relaxations, on/off constraints, and integer cuts. Numerical experiments are conducted on the traditional Belgian gas network, as well as other real larger networks. The results demonstrate both the accuracy and computational speed of the relaxation and its ability to produce high-quality solutions.
Deep CNN Ensemble with Data Augmentation for Object Detection
Venue: arXiv cs.CV 2015
Year: 2015

We report on the methods used in our recent DeepEnsembleCoco submission to the PASCAL VOC 2012 challenge, which achieves state-of-the-art performance on the object detection task. Our method is a variant of the R-CNN model proposed Girshick:CVPR14 with two key improvements to training and evaluation. First, our method constructs an ensemble of deep CNN models with different architectures that are complementary to each other. Second, we augment the PASCAL VOC training set with images from the Microsoft COCO dataset to significantly enlarge the amount training data. Importantly, we select a subset of the Microsoft COCO images to be consistent with the PASCAL VOC task. Results on the PASCAL VOC evaluation server show that our proposed method outperform all previous methods on the PASCAL VOC 2012 detection task at time of submission.
Distribution of elliptic twins over fixed finite fields: Numerical results
Venue: arXiv cs.CR 2015
Year: 2015

We report numerical results, and describe plans for future experiments, related to the number of prime-order curves and "elliptic twin" curves over the primes P-224, P-256, and P-384 standardized by NIST for cryptographic applications. Although these results are not sufficient to confirm the formula of Shparlinski and Sutantyo 2014 over these fields, they strongly suggest (~99% probability) that the NIST curve P-384 was not chosen from a uniform distribution over prime-order curves.
Polyhedral aspects of Submodularity, Convexity and Concavity
Venue: arXiv cs.DM 2015
Year: 2015

Seminal work by Edmonds and Lovasz shows the strong connection between submodularity and convexity. Submodular functions have tight modular lower bounds, and subdifferentials in a manner akin to convex functions. They also admit poly-time algorithms for minimization and satisfy the Fenchel duality theorem and the Discrete Seperation Theorem, both of which are fundamental characteristics of convex functions. Submodular functions also show signs similar to concavity. Submodular maximization, though NP hard, admits constant factor approximation guarantees. Concave functions composed with modular functions are submodular, and they also satisfy diminishing returns property. This manuscript provides a more complete picture on the relationship between submodularity with convexity and concavity, by extending many of the results connecting submodularity with convexity to the concave aspects of submodularity. We first show the existence of superdifferentials, and efficiently computable tight modular upper bounds of a submodular function. While we show that it is hard to characterize this polyhedron, we obtain inner and outer bounds on the superdifferential along with certain specific and useful supergradients. We then investigate forms of concave extensions of submodular functions and show interesting relationships to submodular maximization. We next show connections between optimality conditions over the superdifferentials and submodular maximization, and show how forms of approximate optimality conditions translate into approximation factors for maximization. We end this paper by studying versions of the discrete seperation theorem and the Fenchel duality theorem when seen from the concave point of view. In every case, we relate our results to the existing results from the convex point of view, thereby improving the analysis of the relationship between submodularity, convexity, and concavity.
Salient Object Detection via Objectness Measure
Venue: arXiv cs.CV 2015
Year: 2015

Salient object detection has become an important task in many image processing applications. The existing approaches exploit background prior and contrast prior to attain state of the art results. In this paper, instead of using background cues, we estimate the foreground regions in an image using objectness proposals and utilize it to obtain smooth and accurate saliency maps. We propose a novel saliency measure called `foreground connectivity' which determines how tightly a pixel or a region is connected to the estimated foreground. We use the values assigned by this measure as foreground weights and integrate these in an optimization framework to obtain the final saliency maps. We extensively evaluate the proposed approach on two benchmark databases and demonstrate that the results obtained are better than the existing state of the art approaches.
Simulating the Effects of Various Road Infrastructure Improvements to Vehicular Traffic in a Busy Three-road Fork
Venue: arXiv cs.CE 2015
Year: 2015

Using microsimulations of vehicular dynamics, we studied the effects of several proposed infrastructure developments to the mean travel delay time~$Δ$ and mean speed~$Σ$ of vehicles passing a busy three-road fork, particularly in the non-signalized roundabout junction of Lower Bicutan, Taguig City, Metro Manila. We designed and implemented multi-agent-based microsimulation models to mimic the autonomous driving behavior of heterogeneous individuals and measured the effect of various proposed infrastructure developments on~$Δ$ and~$Σ$. Our aim is to find out the best infrastructure development from among three choices being considered by the local government for the purpose of solving the traffic problems in the area. We created simulation models of the current vehicular traffic situation in the area using the mean travel times~$τ$ of statistically sampled vehicles to show that our model can simulate the real-world at a significance level of $α=0.05$. Based on these models, we then simulated the effect of the proposed infrastructure developments on~$Δ$ and~$Σ$ and used these metrics as our basis of comparison. We found out that the proposed widening of one fork from two lanes to three lanes has the most improved metrics at the same $α=0.05$ compared to the metrics we observed in the current situation. Under this infrastructure development, the~$Δ$ increases linearly ($R^2=0.98$) at the rate of 1.03~$s$, while the~$Σ$ decreases linearly ($R^2>0.99$) at the rate of 0.14~$km/h$ per percent increase in the total vehicle volume~$\mathcal{V}$.
Distributed Wideband Spectrum Sensing
Venue: arXiv cs.IT 2015
Year: 2015

We consider the problem of reconstructing wideband frequency spectra from distributed, compressive measurements. The measurements are made by a network of nodes, each independently mixing the ambient spectra with low frequency, random signals. The reconstruction takes place via local transmissions between nodes, each performing simple statistical operations such as ridge regression and shrinkage.