:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Authors:	Ivanov, Sergiu, Regnault, Damien
Format:	Preprint
Published:	2024
Subjects:	Computational Complexity
Online Access:	https://arxiv.org/abs/2405.18630
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Phase transition in the computational complexity of the shortest common superstring and genome assembly
by: Fernandez, L. A., et al.
Published: (2022)

Efficient LP warmstarting for linear modifications of the constraint matrix
by: Derval, Guillaume, et al.
Published: (2025)

Undecidability of tiling the plane with a fixed number of Wang bars
by: Yang, Chao, et al.
Published: (2024)

Rank Bounds and PIT for $Σ^3 ΠΣΠ^d$ circuits via a non-linear Edelstein-Kelly theorem
by: Garg, Abhibhav, et al.
Published: (2025)

Matrices with displacement structure: a deterministic approach for linear systems and nullspace bases
by: Khichane, Sara, et al.
Published: (2026)

A proof of Ollinger's conjecture: undecidability of tiling the plane with a set of $8$ polyominoes
by: Yang, Chao, et al.
Published: (2024)

Structural insights into the assembly and energy transfer of haptophyte photosystem I-light-harvesting supercomplex.
by: He, Fei-Yu, et al.
Published: (2024)

Decision algorithms for reversibility of one-dimensional non-linear cellular automata under null boundary conditions
by: Junchi, Ma, et al.
Published: (2024)

A lower bound on the field size of convolutional codes with a maximum distance profile and an improved construction
by: Chen, Zitan
Published: (2023)

Space-bounded quantum interactive proof systems
by: Gall, François Le, et al.
Published: (2024)

Quasi-linear time decoding of RS and AG codes for burst errors up to the Singleton bound
by: Li, Songsong, et al.
Published: (2025)

An exposition of recent list-size bounds of FRS Codes
by: Garg, Abhibhav, et al.
Published: (2025)

Pseudorandomness, symmetry, smoothing: I
by: Derksen, Harm, et al.
Published: (2024)

Pseudorandomness, symmetry, smoothing: II
by: Derksen, Harm, et al.
Published: (2024)

Lower bounds for planar Arithmetic Circuits
by: Ramya, C., et al.
Published: (2025)

Sketching approximability of all finite CSPs
by: Chou, Chi-Ning, et al.
Published: (2021)

A note on Jerabek's paper "A simplified lower bound for implicational logic"
by: Gordeev, Lev, et al.
Published: (2026)

Exponential lower bound via exponential sums
by: Bhattacharjee, Somnath, et al.
Published: (2026)

Simple general magnification of circuit lower bounds
by: Atserias, Albert, et al.
Published: (2025)

Resilient functions: Optimized, simplified, and generalized
by: Ivanov, Peter, et al.
Published: (2024)

Depth lower bounds in Stabbing Planes for combinatorial principles
by: Dantchev, Stefan, et al.
Published: (2021)

A nearly-$4\log n$ depth lower bound for formulas with restriction on top
by: Wu, Hao
Published: (2024)

Faster search for tensor decomposition over finite fields
by: Yang, Jason
Published: (2025)

The PCP-like Theorem for Sub-linear Time Inapproximability
by: Ma, Hengzhao, et al.
Published: (2021)

Low-soundness direct-product testers and PCPs from Kaufman--Oppenheim complexes
by: O'Donnell, Ryan, et al.
Published: (2025)

The computational power of discrete chemical reaction networks with bounded executions
by: Doty, David, et al.
Published: (2024)

New results in canonical polyadic decomposition over finite fields
by: Yang, Jason
Published: (2025)

Fourier growth of structured $\mathbb{F}_2$-polynomials and applications
by: Błasiok, Jarosław, et al.
Published: (2021)

Fixed-parameter tractability of canonical polyadic decomposition over finite fields
by: Yang, Jason
Published: (2024)

Computing the $D$-base and $D$-relation in finite closure systems
by: Adaricheva, Kira, et al.
Published: (2024)

Circuit metaconstruction in logspace for Rice-like complexity lower bounds in ANs and SGRs
by: Goubault-Larrecq, Aliénor, et al.
Published: (2025)

Decision DNNFs with imbalanced conjunction cannot efficiently represent CNFs of bounded width
by: Razgon, Igor
Published: (2025)

Depth-first search for tensor rank and border rank over finite fields
by: Yang, Jason
Published: (2024)

A parameterized linear formulation of the integer hull
by: Eisenbrand, Friedrich, et al.
Published: (2025)

Disjunctive Complexity
by: Ivanov, Nikita, et al.
Published: (2025)

Encoding of algebraic geometry codes with quasi-linear complexity $O(N\log N)$
by: Li, Songsong, et al.
Published: (2024)

Approximating 1-in-3 SAT by linearly ordered hypergraph 3-colouring is NP-hard
by: Krokhin, Andrei, et al.
Published: (2025)

Pseudorandom bits for non-commutative programs
by: Lee, Chin Ho, et al.
Published: (2025)

$C_{2k+1}$-coloring of bounded-diameter graphs
by: Piecyk, Marta
Published: (2024)

Structural basis for the assembly and energy transfer between the cyanobacterial PSI core and the double-layered IsiA proteins.
by: Si, Long, et al.
Published: (2025)