Top 10 Arxiv Papers Today in Computational Complexity


0.0 Mikeys
#1. Improved Inapproximability of Rainbow Coloring
Per Austrin, Amey Bhangale, Aditya Potukuchi
A rainbow $q$-coloring of a $k$-uniform hypergraph is a $q$-coloring of the vertex set such that every hyperedge contains all $q$ colors. We prove that given a rainbow $(k - 2\lfloor \sqrt{k}\rfloor)$-colorable $k$-uniform hypergraph, it is NP-hard to find a normal $2$-coloring. Previously, this was only known for rainbow $\lfloor k/2 \rfloor$-colorable hypergraphs (Guruswami and Lee, SODA 2015). We also study a generalization which we call rainbow $(q, p)$-coloring, defined as a coloring using $q$ colors such that every hyperedge contains at least $p$ colors. We prove that given a rainbow $(k - \lfloor \sqrt{kc} \rfloor, k- \lfloor3\sqrt{kc} \rfloor)$-colorable $k$ uniform hypergraph, it is NP-hard to find a normal $c$-coloring for any constant $c < k/10$. The proof of our second result relies on two combinatorial theorems. One of the theorems was proved by Sarkaria (J.~Comb.~Theory.~1990) using topological methods and the other theorem we prove using a generalized Borsuk-Ulam theorem.
more | pdf | html
Figures
None.
Tweets
MathPaper: Improved Inapproximability of Rainbow Coloring. https://t.co/cKHqAlDqFP
el0j: https://t.co/2KKULetosz
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 3
Total Words: 13077
Unqiue Words: 2541

0.0 Mikeys
#2. A Kernel Method for Positive 1-in-3-SAT
Valentin Bura
This paper illustrates the power of Gaussian Elimination by adapting it to Positive 1-in-3-SAT. We derive a general kernelization method for this problem and thus obtain an upper bound for the complexity of its counting version of O(2kR 2^{(1-k)R}) for number of variables R and clauses-to-variables ratio k. Combining this method with previous results gives a time and space complexity for the counting problem of O(4/3|V|2^{3|V|/8}) and O(4/3|V|2^{3|V|/16}).
more | pdf | html
Figures
None.
Tweets
ComputerPapers: A Kernel Method for Positive 1-in-3-SAT. https://t.co/6UBSRvb0QN
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 1
Total Words: 2901
Unqiue Words: 941

0.0 Mikeys
#3. Algorithmic No-Cloning Theorem
Samuel Epstein
We introduce the notions of algorithmic mutual information and rarity of quantum states. These definitions enjoy conservation inequalities over unitary transformations and partial traces. We show that a large majority of pure states have minute self algorithmic information. We provide an algorithmic variant to the no-cloning theorem, by showing that only a small minority of quantum pure states can clone a non negligible amount of algorithmic information. We also provide a chain rule inequality for quantum algorithmic entropy. We show that rarity does not increase under POVM measurements.
more | pdf | html
Figures
None.
Tweets
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 1
Total Words: 4725
Unqiue Words: 1247

0.0 Mikeys
#4. Stable divisorial gonality is in NP
Hans L. Bodlaender, Marieke van der Wegen, Tom C. van der Zanden
Divisorial gonality and stable divisorial gonality are graph parameters, which have an origin in algebraic geometry. Divisorial gonality of a connected graph $G$ can be defined with help of a chip firing game on $G$. The stable divisorial gonality of $G$ is the minimum divisorial gonality over all subdivisions of edges of $G$. In this paper we prove that deciding whether a given connected graph has stable divisorial gonality at most a given integer $k$ belongs to the class NP. Combined with the result that (stable) divisorial gonality is NP-hard by Gijswijt, we obtain that stable divisorial gonality is NP-complete. The proof consist of a partial certificate that can be verified by solving an Integer Linear Programming instance. As a corollary, we have that the number of subdivisions needed for minimum stable divisorial gonality of a graph with $n$ vertices is bounded by $2^{p(n)}$ for a polynomial $p$.
more | pdf | html
Figures
None.
Tweets
M157q_News_RSS: Stable divisorial gonality is in NP. (arXiv:1808.06921v1 [https://t.co/v2KswNHWZT]) https://t.co/RGFofFAIGT Divisorial gonality and stable divisorial gonality
MathPaper: Stable divisorial gonality is in NP. https://t.co/k4i3XR4jUg
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 3
Total Words: 8082
Unqiue Words: 1317

0.0 Mikeys
#5. PPP-Completeness with Connections to Cryptography
Katerina Sotiraki, Manolis Zampetakis, Giorgos Zirdelis
Polynomial Pigeonhole Principle (PPP) is an important subclass of TFNP with profound connections to the complexity of the fundamental cryptographic primitives: collision-resistant hash functions and one-way permutations. In contrast to most of the other subclasses of TFNP, no complete problem is known for PPP. Our work identifies the first PPP-complete problem without any circuit or Turing Machine given explicitly in the input, and thus we answer a longstanding open question from [Papadimitriou1994]. Specifically, we show that constrained-SIS (cSIS), a generalized version of the well-known Short Integer Solution problem (SIS) from lattice-based cryptography, is PPP-complete. In order to give intuition behind our reduction for constrained-SIS, we identify another PPP-complete problem with a circuit in the input but closely related to lattice problems. We call this problem BLICHFELDT and it is the computational problem associated with Blichfeldt's fundamental theorem in the theory of lattices. Building on the inherent connection...
more | pdf | html
Figures
Tweets
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 3
Total Words: 21937
Unqiue Words: 3762

0.0 Mikeys
#6. Resolution and the binary encoding of combinatorial principles
Stefan Dantchev, Nicola Galesi, Barnaby Martin
We investigate the size complexity of proofs in $Res(s)$ -- an extension of Resolution working on $s$-DNFs instead of clauses -- for families of contradictions given in the {\em unusual binary} encoding. A motivation of our work is size lower bounds of refutations in Resolution for families of contradictions in the usual unary encoding. Our main interest is the $k$-Clique Principle, whose Resolution complexity is still unknown. Our main result is a $n^{\Omega(k)}$ lower bound for the size of refutations of the binary $k$-Clique Principle in $Res(\lfloor \frac{1}{2}\log \log n\rfloor)$. This improves the result of Lauria, Pudl\'ak et al. [24] who proved the lower bound for Resolution, that is $Res(1)$. Our second lower bound proves that in $RES(s)$ for $s\leq \log^{\frac{1}{2-\epsilon}}(n)$, the shortest proofs of the $BinPHP^m_n$, requires size $2^{n^{1-\delta}}$, for any $\delta>0$. Furthermore we prove that $BinPHP^m_n$ can be refuted in size $2^{\Theta(n)}$ in treelike $Res(1)$, contrasting with the unary case, where...
more | pdf | html
Figures
None.
Tweets
ComputerPapers: Resolution and the binary encoding of combinatorial principles. https://t.co/MnINh3QeoD
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 3
Total Words: 12434
Unqiue Words: 2521

0.0 Mikeys
#7. Near-optimal Bootstrapping of Hitting Sets for Algebraic Circuits
Mrinal Kumar, Ramprasad Saptharishi, Anamay Tengse
The classical lemma of Ore-DeMillo-Lipton-Schwartz-Zippel states that any nonzero polynomial $f(x_1,\ldots, x_n)$ of degree at most $s$ will evaluate to a nonzero value at some point on a grid $S^n \subseteq \mathbb{F}^n$ with $|S| > s$. Thus, there is a deterministic polynomial identity test (PIT) for all degree-$s$ size-$s$ algebraic circuits in $n$ variables that runs in time $\mathrm{poly}(s) \cdot (s+1)^n$. In a surprising recent result, Agrawal, Ghosh and Saxena (STOC 2018) showed any deterministic blackbox PIT algorithm for degree-$s$, size-$s$, $n$-variate circuits with running time as bad as $s^{n^{0.5 - \delta}}\mathrm{Huge}(n)$, where $\delta > 0$ and $\mathrm{Huge}(n)$ is an arbitrary function, can be used to construct blackbox PIT algorithms for degree-$s$ size $s$ circuits with running time $s^{\exp \circ \exp (O(\log ^\ast s))}$. The authors asked if a similar conclusion followed if their hypothesis was weakened to having deterministic PIT with running time $s^{o(n)}\cdot \mathrm{Huge}(n)$. In this paper, we...
more | pdf | html
Figures
None.
Tweets
ComputerPapers: Near-optimal Bootstrapping of Hitting Sets for Algebraic Circuits. https://t.co/7mEaCgrMPQ
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 3
Total Words: 6252
Unqiue Words: 1567

0.0 Mikeys
#8. Computational Aspects of Optimal Strategic Network Diffusion
Marcin Waniek, Khaled Elbassioni, Flavio L. Pinheiro, Cesar A. Hidalgo, Aamena Alshamsi
The diffusion of information has been widely modeled as stochastic diffusion processes on networks. Alshamsi et al. (2018) proposed a model of strategic diffusion in networks of related activities. In this work we investigate the computational aspects of finding the optimal strategy of strategic diffusion. We prove that finding an optimal solution to the problem is NP-complete in a general case. To overcome this computational difficulty, we present an algorithm to compute an optimal solution based on a dynamic programming technique. We also show that the problem is fixed parameter-tractable when parametrized by the product of the treewidth and maximum degree. We analyze the possibility of developing an efficient approximation algorithm and show that two heuristic algorithms proposed so far cannot have better than a logarithmic approximation guarantee. Finally, we prove that the problem does not admit better than a logarithmic approximation, unless P=NP.
more | pdf | html
Figures
None.
Tweets
ComputerPapers: Computational Aspects of Optimal Strategic Network Diffusion. https://t.co/v43QJkyyPd
SRoyLee: Computational Aspects of Optimal Strategic Network Diffusion - https://t.co/j9kdTkyT9s
SRoyLee: Computational Aspects of Optimal Strategic Network Diffusion - https://t.co/j9kdTkyT9s
SRoyLee: Computational Aspects of Optimal Strategic Network Diffusion - https://t.co/j9kdTkyT9s
SRoyLee: Computational Aspects of Optimal Strategic Network Diffusion - https://t.co/j9kdTkyT9s
SRoyLee: Computational Aspects of Optimal Strategic Network Diffusion - https://t.co/j9kdTkyT9s
SRoyLee: Computational Aspects of Optimal Strategic Network Diffusion - https://t.co/j9kdTkyT9s
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 5
Total Words: 10930
Unqiue Words: 2077

0.0 Mikeys
#9. Expressing Linear Orders Requires Exponential-Size DNNFs
Ronald de Haan
We show that any DNNF circuit that expresses the set of linear orders over a set of $n$ candidates must be of size $2^{\Omega(n)}$.
more | pdf | html
Figures
None.
Tweets
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 1
Total Words: 3464
Unqiue Words: 897

0.0 Mikeys
#10. Polynomial-time Recognition of 4-Steiner Powers
Guillaume Ducoffe
The kth-power of a given graph G=(V,E) is obtained from G by adding an edge between every two distinct vertices at a distance at most k in G. We call G a k-Steiner power if it is an induced subgraph of the kth-power of some tree. Our main contribution is a polynomial-time recognition algorithm of 4-Steiner powers, thereby extending the decade-year-old results of (Lin, Kearney and Jiang, ISAAC'00) for k=1,2 and (Chang and Ko, WG'07) for k=3. A graph G is termed k-leaf power if there is some tree T such that: all vertices in V(G) are leaf-nodes of T, and G is an induced subgraph of the kth-power of T. As a byproduct of our main result, we give the first known polynomial-time recognition algorithm for 6-leaf powers.
more | pdf | html
Figures
Tweets
ComputerPapers: Polynomial-time Recognition of 4-Steiner Powers. https://t.co/d6G0TgjeIs
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 1
Total Words: 29522
Unqiue Words: 3222

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 72,995 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 72,995 papers.