Top 6 Arxiv Papers Today in Computational Complexity


2.002 Mikeys
#1. Metric Dimension Parameterized by Treewidth
Édouard Bonnet, Nidhi Purohit
A resolving set $S$ of a graph $G$ is a subset of its vertices such that no two vertices of $G$ have the same distance vector to $S$. The Metric Dimension problem asks for a resolving set of minimum size, and in its decision form, a resolving set of size at most some specified integer. This problem is NP-complete, and remains so in very restricted classes of graphs. It is also W[2]-complete with respect to the size of the solution. Metric Dimension has proven elusive on graphs of bounded treewidth. On the algorithmic side, a polytime algorithm is known for trees, and even for outerplanar graphs, but the general case of treewidth at most two is open. On the complexity side, no parameterized hardness is known. This has led several papers on the topic to ask for the parameterized complexity of Metric Dimension with respect to treewidth. We provide a first answer to the question. We show that Metric Dimension parameterized by the treewidth of the input graph is W[1]-hard. More refinedly we prove that, unless the Exponential...
more | pdf | html
Figures
None.
Tweets
okateim: 2019/07/19 [7] Metric Dimension Parameterized by Treewidth (https://t.co/VpA6gwyolE)
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 2
Total Words: 0
Unqiue Words: 0

1.997 Mikeys
#2. Interesting Open Problem Related to Complexity of Computing the Fourier Transform and Group Theory
Nir Ailon
The Fourier Transform is one of the most important linear transformations used in science and engineering. Cooley and Tukey's Fast Fourier Transform (FFT) from 1964 is a method for computing this transformation in time $O(n\log n)$. From a lower bound perspective, relatively little is known. Ailon shows in 2013 an $\Omega(n\log n)$ bound for computing the normalized Fourier Transform assuming only unitary operations on pairs of coordinates is allowed. The goal of this document is to describe a natural open problem that arises from this work, which is related to group theory, and in particular to representation theory.
more | pdf | html
Figures
None.
Tweets
NPunuvar: Interesting Open Problem Related to Complexity of Computing the Fourier Transform and Group Theory https://t.co/4o9vKCFVHD
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 1
Total Words: 1579
Unqiue Words: 604

1.997 Mikeys
#3. Almost tight bound on the query complexity of generalized Simon's problem
Zekun Ye, Yunqi Huang, Yuyi Wang, Lvzhou Li
Simon's problem played an important role in the history of quantum algorithms, as it inspired Shor to discover the celebrated quantum algorithm solving integer factorization in polynomial time. Besides, the quantum algorithm for Simon's problem has been recently applied to break symmetric cryptosystems. Generalized Simon's problem is a natural extension of Simon's problem: Given a function $f:\{0,1\}^n \to \{0,1\}^m$ with $n \le m$ and the promise that there exists a subgroup $S \le \mathbb{Z}_2^n$ of rank $k$ s.t. for any $s, x\in\{0,1\}^n, f(x) = f(x\oplus s)$ iff $s\in S$, the goal is to find $S$. It is not difficult to design a quantum algorithm for solving this problem exactly with query complexity of $O(n-k)$. However, so far it is not clear what is the classical deterministic query complexity of this problem. % Therefore, it is interesting and nontrivial to consider that, not only for clarifying the gap between quantum and classical computing on this problem, but also from the viewpoint of classical computing. In this...
more | pdf | html
Figures
None.
Tweets
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 4
Total Words: 7682
Unqiue Words: 1588

1.995 Mikeys
#4. On the $\text{AC}^0[\oplus]$ complexity of Andreev's Problem
Aditya Potukuchi
Andreev's Problem states the following: Given an integer $d$ and a subset of $S \subseteq \mathbb{F}_q \times \mathbb{F}_q$, is there a polynomial $y = p(x)$ of degree at most $d$ such that for every $a \in \mathbb{F}_q$, $(a,p(a)) \in S$? We show an $\text{AC}^0[\oplus]$ lower bound for this problem. This problem appears to be similar to the list recovery problem for degree $d$-Reed-Solomon codes over $\mathbb{F}_q$ which states the following: Given subsets $A_1,\ldots,A_q$ of $\mathbb{F}_q$, output all (if any) the Reed-Solomon codewords contained in $A_1\times \cdots \times A_q$. For our purpose, we study this problem when $A_1, \ldots, A_q$ are random subsets of a given size, which may be of independent interest.
more | pdf | html
Figures
None.
Tweets
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 1
Total Words: 8905
Unqiue Words: 1996

1.995 Mikeys
#5. Imperfect Gaps in Gap-ETH and PCPs
Mitali Bafna, Nikhil Vyas
We study the role of perfect completeness in probabilistically checkable proof systems (PCPs) and give a new way to transform a PCP with imperfect completeness to a PCP with perfect completeness when the initial gap is a constant. In particular, we show that $\text{PCP}_{c,s}[r,q] \subseteq \text{PCP}_{1,1-\Omega(1)}[r+O(1),q+O(r)]$, for $c-s=\Omega(1)$. This implies that one can convert imperfect completeness to perfect in linear-sized PCPs for $NTIME[O(n)]$ with a $O(\log n)$ additive loss in the query complexity $q$. We show our result by constructing a "robust circuit" using threshold gates. These results are a gap amplification procedure for PCPs (when completeness is imperfect), analogous to questions studied in parallel repetition and pseudorandomness. We also investigate the time complexity of approximating perfectly satisfiable instances of 3SAT versus those with imperfect completeness. We show that the Gap-ETH conjecture without perfect completeness is equivalent to Gap-ETH with perfect completeness, i.e. we show that...
more | pdf | html
Figures
None.
Tweets
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 2
Total Words: 0
Unqiue Words: 0

1.995 Mikeys
#6. Approximate counting CSP seen from the other side
Andrei A. Bulatov, Stanislav Zivny
In this paper we study the complexity of counting Constraint Satisfaction Problems (CSPs) of the form #CSP($\mathcal{C}$,-), in which the goal is, given a relational structure $\mathbf{A}$ from a class $\mathcal{C}$ of structures and an arbitrary structure $\mathbf{B}$, to find the number of homomorphisms from $\mathbf{A}$ to $\mathbf{B}$. Flum and Grohe showed that #CSP($\mathcal{C}$,-) is solvable in polynomial time if $\mathcal{C}$ has bounded treewidth [FOCS'02]. Building on the work of Grohe [JACM'07] on decision CSPs, Dalmau and Jonsson then showed that, if $\mathcal{C}$ is a recursively enumerable class of relational structures of bounded arity, then assuming FPT $\neq$ #W[1], there are no other cases of #CSP($\mathcal{C}$,-) solvable exactly in polynomial time (or even fixed-parameter time) [TCS'04]. We show that, assuming FPT $\neq$ W[1] (under randomised parametrised reductions) and for $\mathcal{C}$ satisfying certain general conditions, #CSP($\mathcal{C}$,-) is not solvable even approximately for $\mathcal{C}$...
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 160,435 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 160,435 papers.