Top 4 Arxiv Papers Today in Computational Complexity


2.012 Mikeys
#1. Inapproximability within W[1]: the case of Steiner Orientation
Michal Wlodarczyk
In the $k$-Steiner Orientation problem we are given a mixed graph, that is, with both directed and undirected edges, and a set of $k$ terminal pairs. The goal is to find an orientation of the undirected edges that maximizes the number of terminal pairs for which there is a path from the source to the sink. The problem is known to be W[1]-hard when parameterized by $k$ and hard to approximate up to some constant for FPT algorithms assuming Gap-ETH. On the other hand, no approximation better than $O(k)$ is known. We show that $k$-Steiner Orientation admits no sublogarithmic approximation algorithm, even with a parameterized running time, assuming W[1] $\ne$ FPT. To obtain this result, we reduce the problem to itself via a hashing-based gap amplification technique, which turns out useful even outside of the FPT paradigm. Precisely, we rule out any approximation ratio of the form $(\log k)^{o(1)}$ for parameterized algorithms and $(\log n)^{o(1)}$ for purely polynomial running time, under the same assumption. This constitutes a...
more | pdf | html
Figures
None.
Tweets
okateim: 2019/07/16 [13] Inapproximability within W[1]: the case of Steiner Orientation (https://t.co/bQ8zJcYPAE)
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 1
Total Words: 0
Unqiue Words: 0

2.005 Mikeys
#2. Efficient methods to determine the reversibility of general 1D linear cellular automata in polynomial complexity
Xinyu Du, Chao Wang, Tianze Wang, Zeyu Gao
In this paper, we study reversibility of one-dimensional(1D) linear cellular automata(LCA) under null boundary condition, whose core problems have been divided into two main parts: calculating the period of reversibility and verifying the reversibility in a period. With existing methods, the time and space complexity of these two parts are still too expensive to be employed. So the process soon becomes totally incalculable with a slightly big size, which greatly limits its application. In this paper, we set out to solve these two problems using two efficient algorithms, which make it possible to solve reversible LCA of very large size. Furthermore, we provide an interesting perspective to conversely generate 1D LCA from a given period of reversibility. Due to our methods' efficiency, we can calculate the reversible LCA with large size, which has much potential to enhance security in cryptography system.
more | pdf | html
Figures
Tweets
SciencePapers: Efficient methods to determine the reversibility of general 1D linear cellular automata in polynomial complexity. https://t.co/Zk2JYtrJyQ
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 4
Total Words: 9213
Unqiue Words: 1987

1.995 Mikeys
#3. The Projection Games Conjecture and the Hardness of Approximation of SSAT and related problems
Priyanka Mukhopadhyay
The Super-SAT or SSAT problem was introduced by Dinur, Kindler, Raz and Safra[2002,2003] to prove the NP-hardness of approximation of two popular lattice problems - Shortest Vector Problem (SVP) and Closest Vector Problem (CVP). They conjectured that SSAT is NP-hard to approximate to within factor $n^c$ for some constant $c>0$, where $n$ is the size of the SSAT instance. In this paper we prove this conjecture assuming the Projection Games Conjecture (PGC), given by Moshkovitz[2012]. This implies hardness of approximation of SVP and CVP within polynomial factors, assuming the Projection Games Conjecture. We also reduce SSAT to the Nearest Codeword Problem (NCP) and Learning Halfspace Problem (LHP), as considered by Arora, Babai, Stern and Sweedyk[1997]. This proves that both these problems are NP-hard to approximate within factor $N^{c'/\log\log n}$ for some constant $c'>0$ where $N$ is the size of the instances of the respective problems. Assuming the Projection Games Conjecture these problems are proved to be NP-hard to...
more | pdf | html
Figures
None.
Tweets
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 1
Total Words: 12396
Unqiue Words: 2294

1.995 Mikeys
#4. Spherical Discrepancy Minimization and Algorithmic Lower Bounds for Covering the Sphere
Chris Jones, Matt McPartlon
Inspired by the boolean discrepancy problem, we study the following optimization problem which we term \textsc{Spherical Discrepancy}: given $m$ unit vectors $v_1, \dots, v_m$, find another unit vector $x$ that minimizes $\max_i \langle x, v_i\rangle$. We show that \textsc{Spherical Discrepancy} is APX-hard and develop a multiplicative weights-based algorithm that achieves nearly optimal worst-case error bounds. We use our algorithm to give the first non-trivial lower bounds for the problem of covering a hypersphere by hyperspherical caps of uniform volume at least $2^{-o(\sqrt{n})}$, and to give a lower bound for covering a Gaussian random variable by equal-sized halfspaces. Up to a log factor, our lower bounds match known upper bounds in this regime. Finally, we show how to modify our algorithm to solve a natural version of the Koml{\'o}s problem for the spherical setting.
more | pdf | html
Figures
None.
Tweets
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 2
Total Words: 0
Unqiue Words: 0

About

Assert is a website where the best academic papers on arXiv (computer science, math, physics), bioRxiv (biology), BITSS (reproducibility), EarthArXiv (earth science), engrXiv (engineering), LawArXiv (law), PsyArXiv (psychology), SocArXiv (social science), and SportRxiv (sport research) bubble to the top each day.

Papers are scored (in real-time) based on how verifiable they are (as determined by their Github repos) and how interesting they are (based on Twitter).

To see top papers, follow us on twitter @assertpub_ (arXiv), @assert_pub (bioRxiv), and @assertpub_dev (everything else).

To see beautiful figures extracted from papers, follow us on Instagram.

Tracking 158,360 papers.

Search
Sort results based on if they are interesting or reproducible.
Interesting
Reproducible
Categories
All
Astrophysics
Cosmology and Nongalactic Astrophysics
Earth and Planetary Astrophysics
Astrophysics of Galaxies
High Energy Astrophysical Phenomena
Instrumentation and Methods for Astrophysics
Solar and Stellar Astrophysics
Condensed Matter
Disordered Systems and Neural Networks
Mesoscale and Nanoscale Physics
Materials Science
Other Condensed Matter
Quantum Gases
Soft Condensed Matter
Statistical Mechanics
Strongly Correlated Electrons
Superconductivity
Computer Science
Artificial Intelligence
Hardware Architecture
Computational Complexity
Computational Engineering, Finance, and Science
Computational Geometry
Computation and Language
Cryptography and Security
Computer Vision and Pattern Recognition
Computers and Society
Databases
Distributed, Parallel, and Cluster Computing
Digital Libraries
Discrete Mathematics
Data Structures and Algorithms
Emerging Technologies
Formal Languages and Automata Theory
General Literature
Graphics
Computer Science and Game Theory
Human-Computer Interaction
Information Retrieval
Information Theory
Machine Learning
Logic in Computer Science
Multiagent Systems
Multimedia
Mathematical Software
Numerical Analysis
Neural and Evolutionary Computing
Networking and Internet Architecture
Other Computer Science
Operating Systems
Performance
Programming Languages
Robotics
Symbolic Computation
Sound
Software Engineering
Social and Information Networks
Systems and Control
Economics
Econometrics
General Economics
Theoretical Economics
Electrical Engineering and Systems Science
Audio and Speech Processing
Image and Video Processing
Signal Processing
General Relativity and Quantum Cosmology
General Relativity and Quantum Cosmology
High Energy Physics - Experiment
High Energy Physics - Experiment
High Energy Physics - Lattice
High Energy Physics - Lattice
High Energy Physics - Phenomenology
High Energy Physics - Phenomenology
High Energy Physics - Theory
High Energy Physics - Theory
Mathematics
Commutative Algebra
Algebraic Geometry
Analysis of PDEs
Algebraic Topology
Classical Analysis and ODEs
Combinatorics
Category Theory
Complex Variables
Differential Geometry
Dynamical Systems
Functional Analysis
General Mathematics
General Topology
Group Theory
Geometric Topology
History and Overview
Information Theory
K-Theory and Homology
Logic
Metric Geometry
Mathematical Physics
Numerical Analysis
Number Theory
Operator Algebras
Optimization and Control
Probability
Quantum Algebra
Rings and Algebras
Representation Theory
Symplectic Geometry
Spectral Theory
Statistics Theory
Mathematical Physics
Mathematical Physics
Nonlinear Sciences
Adaptation and Self-Organizing Systems
Chaotic Dynamics
Cellular Automata and Lattice Gases
Pattern Formation and Solitons
Exactly Solvable and Integrable Systems
Nuclear Experiment
Nuclear Experiment
Nuclear Theory
Nuclear Theory
Physics
Accelerator Physics
Atmospheric and Oceanic Physics
Applied Physics
Atomic and Molecular Clusters
Atomic Physics
Biological Physics
Chemical Physics
Classical Physics
Computational Physics
Data Analysis, Statistics and Probability
Physics Education
Fluid Dynamics
General Physics
Geophysics
History and Philosophy of Physics
Instrumentation and Detectors
Medical Physics
Optics
Plasma Physics
Popular Physics
Physics and Society
Space Physics
Quantitative Biology
Biomolecules
Cell Behavior
Genomics
Molecular Networks
Neurons and Cognition
Other Quantitative Biology
Populations and Evolution
Quantitative Methods
Subcellular Processes
Tissues and Organs
Quantitative Finance
Computational Finance
Economics
General Finance
Mathematical Finance
Portfolio Management
Pricing of Securities
Risk Management
Statistical Finance
Trading and Market Microstructure
Quantum Physics
Quantum Physics
Statistics
Applications
Computation
Methodology
Machine Learning
Other Statistics
Statistics Theory
Feedback
Online
Stats
Tracking 158,360 papers.