Showing posts with the label Stay Up to Date

Avi Wigderson’s 60th Birthday

There is a workshop being organized in honor of Avi Wigderson (incidentally, a founding member of CATCS) on the occasion of his 60th birthday. The website for the workshop is The organizers are Sanjeev Arora, Boaz Barak, Ran Raz, Peter Sarnak, and Amir Shpilka. The workshop will take place at the Institute for Advanced Study, Princeton New Jersey, from Wednesday October 5 till Saturday October 8 2016. The last day will be half a day, joint with FOCS 2016, and will take place at the FOCS hotel. The workshop is open for everyone and free of charge, but registration is required. Please register at: A small fund has been established to provide financial support for students. Funds are limited and those interested in applying for financial support must complete the Funding Support section of the registration form no later than August 1, 2016. This date is firm. Invited Speakers: Scott Aaronson, Dorit Aharonov, Noga Alon, Zeev Dvir, Oded Goldreich…

A Simpler Bit-parallel Algorithm for Swap Matching

Authors: Václav Blažej, Ondřej Suchý, Tomáš Valla Download: PDFAbstract: The pattern matching problem with swaps is to find all occurrences of a pattern in a text while allowing the pattern to swap adjacent symbols. The goal is to design fast matching algorithm that takes advantage of the bit parallelism of bitwise machine instructions. We point out a fatal flaw in the algorithm proposed by Ahmed et al. [The swap matching problem revisited, Theor. Comp. Sci. 2014], which we describe in detail. Furthermore we devise a new swap pattern matching algorithm which is based on the same graph theoretical model as the algorithm by Ahmed et al. (thus still not based on FFT) and we prove its correctness. We also show that an approach using deterministic finite automata cannot achieve similarly efficient algorithms.

from Theory of Computing Blog Aggregator

Efficient data streaming multiway aggregation through concurrent algorithmic designs and new abstract data types

Authors: Vincenzo Gulisano, Yiannis Nikolakopoulos, Daniel Cederman, Marina Papatriantafilou, Philippas Tsigas Download: PDFAbstract: Data streaming relies on continuous queries to process unbounded streams of data in a real-time fashion. It is commonly demanding in computation capacity, given that the relevant applications involve very large volumes of data. Data structures act as articulation points and maintain the state of data streaming operators, potentially supporting high parallelism and balancing the work between them. Prompted by this fact, in this work we study and analyze parallelization needs of these articulation points, focusing on the problem of streaming multiway aggregation, where large data volumes are received from multiple input streams. The analysis of the parallelization needs, as well as of the use and limitations of existing aggregate designs and their data structures, leads us to identify needs for proper shared objects that can achieve low-latency and high t…

Improved Space efficient algorithms for BFS, DFS and applications

Authors: Niranka Banerjee, Sankardeep Chakraborty, Venkatesh Raman Download: PDFAbstract: Recent work by Elmasry et al. (STACS 2015) and Asano et al. (ISAAC 2014), reconsidered classical fundamental graph algorithms focusing on improving the space complexity. We continue this line of work focusing on space. Our first result is a simple data structure that can maintain any subset $S$ of a universe of $n$ elements using $n+o(n)$ bits and support in constant time, apart from the standard insert, delete and membership queries, the operation {\it findany} that finds and returns any element of the set (or outputs that the set is empty). Using this we give a BFS implementation that takes $O(m+n)$ time using at most $2n+o(n)$ bits. Later, we further improve the space requirement of BFS to at most $1.585n + o(n)$ bits. We demonstrate the use of our data structure by developing another data structure using it that can represent a sequence of $n$ non-negative integers $x_1, x_2, \ldots x_n$ usin…

Geodesic Walks on Polytopes

Authors: Yin Tat Lee, Santosh S. Vempala Download: PDFAbstract: We introduce the geodesic walk for sampling Riemannian manifolds and apply it to the problem of generating uniform random points from polytopes in R^n specified by m inequalities. The walk is a discrete-time simulation of a stochastic differential equation (SDE) on the Riemannian manifold equipped with the metric induced by the Hessian of a convex function; each step is the solution of an ordinary differential equation (ODE). The resulting sampling algorithm for polytopes mixes in O*(mn^{3/4}) steps. This is the first walk that breaks the quadratic barrier for mixing in high dimension, improving on the previous best bound of O*(mn) by Kannan and Narayanan for the Dikin walk. We also show that each step of the geodesic walk (solving an ODE) can be implemented efficiently, thus improving the time complexity for sampling polytopes. Our analysis of the geodesic walk for general Hessian manifolds might be of independent intere…

Space-Efficient Biconnected Components and Recognition of Outerplanar Graphs

Authors: Frank Kammer, Dieter Kratsch, Moritz Laudahn Download: PDFAbstract: We present space-efficient algorithms for computing cut vertices in a given graph with $n$ vertices and $m$ edges in linear time using $O(n+\min\{m,n\log \log n\})$ bits. With the same time and using $O(n+m)$ bits, we can compute the biconnected components of a graph. We use this result to show an algorithm for the recognition of (maximal) outerplanar graphs in $O(n\log \log n)$ time using $O(n)$ bits.

from Theory of Computing Blog Aggregator

Trading Determinism for Time in Space Bounded Computations

Authors: Vivek Anand T Kallampally, Raghunath Tewari Download: PDFAbstract: Savitch showed in $1970$ that nondeterministic logspace (NL) is contained in deterministic $\mathcal{O}(\log^2 n)$ space but his algorithm requires quasipolynomial time. The question whether we can have a deterministic algorithm for every problem in NL that requires polylogarithmic space and simultaneously runs in polynomial time was left open. In this paper we give a partial solution to this problem and show that for every language in NL there exists an unambiguous nondeterministic algorithm that requires $\mathcal{O}(\log^2 n)$ space and simultaneously runs in polynomial time.

from Theory of Computing Blog Aggregator

Algebraic Problems Equivalent to Beating Exponent 3/2 for Polynomial Factorization over Finite Fields

Authors: Zeyu Guo, Anand Kumar Narayanan, Chris Umans Download: PDFAbstract: The fastest known algorithm for factoring univariate polynomials over finite fields is the Kedlaya-Umans (fast modular composition) implementation of the Kaltofen-Shoup algorithm. It is randomized and takes $\widetilde{O}(n^{3/2}\log q + n \log^2 q)$ time to factor polynomials of degree $n$ over the finite field $\mathbb{F}_q$ with $q$ elements. A significant open problem is if the $3/2$ exponent can be improved. We study a collection of algebraic problems and establish a web of reductions between them. A consequence is that an algorithm for any one of these problems with exponent better than $3/2$ would yield an algorithm for polynomial factorization with exponent better than $3/2$.

from Theory of Computing Blog Aggregator

String Inference from the LCP Array

Authors: Juha Kärkkäinen, Marcin Piątkowski, Simon J. Puglisi Download: PDFAbstract: The suffix array is often augmented with the longest common prefix (LCP) array which is, in essence, a representation of the suffix tree shape. We consider the problem of inferring a string from an LCP array, i.e., determining whether a given array of integers is a valid LCP array, and if it is, reconstructing some text or all texts with that LCP array. We provide two results. (1) We describe a linear time algorithm for inferring a string from an LCP array that contains a single zero (indicating a binary alphabet). For a valid LCP array the algorithm outputs a Burrows-Wheeler transform (BWT), the inversion of which produces a collection of cyclic strings whose generalized LCP array is identical to the input. Furthermore, the algorithm outputs a linear size representation of all such BWTs. (2) We prove that determining whether one of the valid BWTs produced by the above algorithm inverts to a single (c…

Settling the complexity of computing approximate two-player Nash equilibria

Authors: Aviad Rubinstein Download: PDFAbstract: We prove that there exists a constant $\epsilon>0$ such that, assuming the Exponential Time Hypothesis for PPAD, computing an $\epsilon$-approximate Nash equilibrium in a two-player (nXn) game requires quasi-polynomial time, $n^{\log^{1-o(1)} n}$. This matches (up to the o(1) term) the algorithm of Lipton, Markakis, and Mehta [LMM03]. Our proof relies on a variety of techniques from the study of probabilistically checkable proofs (PCP); this is the first time that such ideas are used for a reduction between problems inside PPAD. En route, we also prove new hardness results for computing Nash equilibria in games with many players. In particular, we show that computing an $\epsilon$-approximate Nash equilibrium in a game with n players requires $2^{\Omega(n)}$ oracle queries to the payoff tensors. This resolves an open problem posed by Hart and Nisan [HN13], Babichenko [Bab14], and Chen et al. [CCT15]. In fact, our results for n-player…

Polynomial Prestidigitation

Suddenly a sharp bound on progression-free subsets is revealed Ernie Croot, Vsevolod Lev, and Péter Pach (CLP) found a new application of polynomials last month. They proved that every set of size at least has three distinct elements such that . Jordan Ellenberg and Dion Gijswijt extended this to for prime powers . Previous bounds had the form at best. Our friend Gil Kalai and others observed impacts on other mathematical problems including conjectures about sizes of sunflowers. Today we congratulate them—Croot is a colleague of Dick’s in Mathematics at Georgia Tech—and wonder what the breakthroughs involving polynomials might mean for complexity theory. What’s amazing is that the above papers are so short, including a new advance by Ellenberg that is just 2 pages. In his own post on the results, Tim Gowers muses: [The CLP argument presents a stiff challenge to my view that] mathematical ideas always result from a fairly systematic process—and that the opposite impression, that some i…

TR16-097 | Trading Determinism for Time in Space Bounded Computations | Raghunath Tewari, Vivek Anand T Kallampally

Savitch showed in $1970$ that nondeterministic logspace (NL) is contained in deterministic $\mathcal{O}(\log^2 n)$ space but his algorithm requires quasipolynomial time. The question whether we can have a deterministic algorithm for every problem in NL that requires polylogarithmic space and simultaneously runs in polynomial time was left open. In this paper we give a partial solution to this problem and show that for every language in NL there exists an unambiguous nondeterministic algorithm that requires $\mathcal{O}(\log^2 n)$ space and simultaneously runs in polynomial time.

from Theory of Computing Blog Aggregator

Range Majorities and Minorities in Arrays

Authors: Djamal Belazzougui, Travis Gagie, J. Ian Munro, Gonzalo Navarro, Yakov Nekrich Download: PDFAbstract: Karpinski and Nekrich (2008) introduced the problem of parameterized range majority, which asks us to preprocess a string of length $n$ such that, given the endpoints of a range, one can quickly find all the distinct elements whose relative frequencies in that range are more than a threshold $\tau$. Subsequent authors have reduced their time and space bounds such that, when $\tau$ is fixed at preprocessing time, we need either $O(n \log (1 / \tau))$ space and optimal $O(1 / \tau)$ query time or linear space and $O((1 / \tau) \log \log \sigma)$ query time, where $\sigma$ is the alphabet size. In this paper we give the first linear-space solution with optimal $O(1 / \tau)$ query time, even with variable $\tau$ (i.e., specified with the query). For the case when $\sigma$ is polynomial on the computer word size, our space is optimally compressed according to the symbol frequencie…

The Parameterized Complexity of Fixing Number and Vertex Individualization in Graphs

Authors: V. Arvind, Frank Fuhlbrück, Johannes Köbler, Sebastian Kuhnert, Gaurav Rattan Download: PDFAbstract: In this paper we study the complexity of the following problems: Given a colored graph X=(V,E,c), compute a minimum cardinality set S of vertices such that no nontrivial automorphism of X fixes all vertices in S. A closely related problem is computing a minimum base S for a permutation group G on [n] given by generators, i.e., a minimum cardinality subset S of [n] such that no nontrivial permutation in G fixes all elements of S. Our focus is mainly on the parameterized complexity of these problems. We show that when k=|S| is treated as parameter, then both problems are MINI[1]-hard. For the dual problems, where k=n-|S| is the parameter, we give FPT algorithms. A notion closely related to fixing is called individualization. Individualization combined with the Weisfeiler-Leman procedure is a fundamental technique in algorithms for Graph Isomorphism. Motivated by the power of ind…

Problems on One Way Road Networks

Authors: Jammigumpula Ajaykumar, Avinandan Das, Navaneeta Saikia, Arindam Karmakar Download: PDFAbstract: Let $OWRN = \left\langle W_x,W_y \right\rangle$ be a One Way Road Network where $W_x$ and $W_y$ are the sets of directed horizontal and vertical roads respectively. $OWRN$ can be considered as a variation of directed grid graph. The intersection of the horizontal and vertical roads are the vertices of $OWRN$ and any two consecutive vertices on a road is connected by an edge. In this work, we analyze the problem of collision free Traffic configuration in an $OWRN$. A traffic configuration is a two-tuple $TC=\left\langle OWRN, C\right\rangle$, where $C$ is a set of cars travelling on a pre-defined path. We prove that finding a maximum cardinality subset $C_{sub}\subseteq C$ such that $TC=\left\langle OWRN, C_{sub}\right\rangle$ is collision-free, is NP-hard. Lastly we investigate the properties of connectedness, shortest paths in an $OWRN$.

from Theory of Computing Blog Aggregator h…

An Ancilla Based Quantum Simulation Framework for Non-Unitary Matrices

Authors: Ammar Daskin, Sabre Kais Download: PDFAbstract: The success probability in an ancilla based circuit generally decreases exponentially in the number of qubits consisted in the ancilla. Although the probability can be amplified through the amplitude amplification process, the input dependence of the amplitude amplification makes difficult to sequentially combine two or more ancilla based circuits. A new version of the amplitude amplification known as the oblivious amplitude amplification runs independently of the input to the system register. This allow us to to sequentially combine two or more ancilla based circuits. However, this type of the amplification only works when the considered system is unitary or non-unitary but somehow close to a unitary. In this paper, we present a general framework to simulate non-unitary matrices on ancilla based quantum circuits in which the success probability is maximized by using the oblivious amplitude amplification. In particular, we show …

On degeneration of tensors and algebras

Authors: Markus Bläser, Vladimir Lysikov Download: PDFAbstract: An important building block in all current asymptotically fast algorithms for matrix multiplication are tensors with low border rank, that is, tensors whose border rank is equal or very close to their size. To find new asymptotically fast algorithms for matrix multiplication, it seems to be important to understand those tensors whose border rank is as small as possible, so called tensors of minimal border rank. We investigate the connection between degenerations of associative algebras and degenerations of their structure tensors in the sense of Strassen. It allows us to describe an open subset of $n \times n \times n$ tensors of minimal border rank in terms of smoothability of commutative algebras. We describe the smoothable algebra associated to the Coppersmith-Winograd tensor and prove a lower bound for the border rank of the tensor used in the "easy construction" of Coppersmith and Winograd.

from Theory of C…

A revised model of fluid transport optimization in Physarum polycephalum

Authors: Vincenzo Bonifaci Download: PDFAbstract: Optimization of fluid transport in the slime mold Physarum polycephalum has been the subject of several modeling efforts in recent literature. Existing models assume that the tube adaptation mechanism in P. polycephalum's tubular network is controlled by the sheer amount of fluid flow through the tubes. We put forward the hypothesis that the controlling variable may instead be the flow's pressure gradient along the tube. We carry out the stability analysis of such a revised mathematical model for a parallel-edge network, proving that the revised model supports the global flow-optimizing behavior of the slime mold for a substantially wider class of response functions compared to previous models. Simulations also suggest that the same conclusion may be valid for arbitrary network topologies.

from Theory of Computing Blog Aggregator

The Chasm at Depth Four, and Tensor Rank : Old results, new insights

Authors: Suryajith Chillara, Mrinal Kumar, Ramprasad Saptharishi, V Vinay Download: PDFAbstract: Agrawal and Vinay [AV08] showed how any polynomial size arithmetic circuit can be thought of as a depth four arithmetic circuit of subexponential size. The resulting circuit size in this simulation was more carefully analyzed by Korian [Koiran] and subsequently by Tavenas [Tav13]. We provide a simple proof of this chain of results. We then abstract the main ingredient to apply it to formulas and constant depth circuits, and show more structured depth reductions for them. In an apriori surprising result, Raz [Raz10] showed that for any $n$ and $d$, such that $ \omega(1) \leq d \leq O\left(\frac{\log n}{\log\log n}\right)$, constructing explicit tensors $T:[n]^d \rightarrow F$ of high enough rank would imply superpolynomial lower bounds for arithmetic formulas over the field $F$. Using the additional structure we obtain from our proof of the depth reduction for arithmetic formulas, we give a…

Single machine scheduling with job-dependent machine deterioration

Authors: Wenchang Luo, Yao Xu, Weitian Tong, Guohui Lin Download: PDFAbstract: We consider the single machine scheduling problem with job-dependent machine deterioration. In the problem, we are given a single machine with an initial non-negative maintenance level, and a set of jobs each with a non-preemptive processing time and a machine deterioration. Such a machine deterioration quantifies the decrement in the machine maintenance level after processing the job. To avoid machine breakdown, one should guarantee a non-negative maintenance level at any time point; and whenever necessary, a maintenance activity must be allocated for restoring the machine maintenance level. The goal of the problem is to schedule the jobs and the maintenance activities such that the total completion time of jobs is minimized. There are two variants of maintenance activities: in the partial maintenance case each activity can be allocated to increase the machine maintenance level to any level not exceeding t…