:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Authors:	Filmus, Yuval, Meir, Or, Tal, Avishay
Format:	Preprint
Published:	2020
Subjects:	Computational Complexity 68Q06 F.1.1
Online Access:	https://arxiv.org/abs/2012.02210
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Near-Optimal Bootstrapping of Hitting Sets for Algebraic Models
by: Kumar, Mrinal, et al.
Published: (2018)

Bounded Distance Decoding for Random Lattices
by: Gao, Shuhong
Published: (2025)

Smaller Depth-2 Linear Circuits for Disjointness Matrices
by: Ye, Lixi
Published: (2026)

Upper and Lower Bounds for the Linear Ordering Principle
by: Hirsch, Edward A., et al.
Published: (2025)

CLIQUE as an AND of Polynomial-Sized Monotone Constant-Depth Circuits
by: Bodnar, Levente
Published: (2024)

Red-Blue Pebbling with Multiple Processors: Time, Communication and Memory Trade-offs
by: Böhnlein, Toni, et al.
Published: (2024)

The Complexity of Iterated Reversible Computation
by: Eppstein, David
Published: (2021)

Commutative N-polyregular functions
by: Lopez, Aliaume
Published: (2024)

Explicit separations between randomized and deterministic Number-on-Forehead communication
by: Kelley, Zander, et al.
Published: (2023)

An MDL-Style Cost Functional KC, Distribution-Preserving Reductions ($A2^d$), and an $AC^0$+log Lower Bound for 3SAT via Balanced 3XOR
by: Lela, Marko
Published: (2025)

The Serial Scaling Hypothesis
by: Liu, Yuxi, et al.
Published: (2025)

Psi-Turing Machines: Bounded Introspection for Complexity Barriers and Oracle Separations
by: Huseynzade, Rafig
Published: (2025)

Insignificant Choice Polynomial Time: A Logic Capturing PTIME
by: Schewe, Klaus-Dieter
Published: (2020)

On the existence of strong proof complexity generators
by: Krajicek, Jan
Published: (2022)

Extended Nullstellensatz proof systems
by: Krajicek, Jan
Published: (2023)

Stochastic well-structured transition systems
by: Aspnes, James
Published: (2025)

Catalytic Computing and Register Programs Beyond Log-Depth
by: Alekseev, Yaroslav, et al.
Published: (2025)

Functional Closure Properties of Finite $\mathbb{N}$-weighted Automata
by: Dörfler, Julian, et al.
Published: (2024)

Toward Better Depth Lower Bounds: A KRW-like theorem for Strong Composition
by: Meir, Or
Published: (2023)

Polynomial Prenexing of QBFs with Non-Monotone Boolean Operators
by: Saffidine, Abdallah, et al.
Published: (2025)

Classically Time-Controlled Quantum Automata: Definition and Properties
by: Díaz-Caro, Alejandro, et al.
Published: (2018)

Functional Lower Bounds in Algebraic Proofs: Symmetry, Lifting, and Barriers
by: Hakoniemi, Tuomas, et al.
Published: (2024)

Algorithmic Barriers to Detecting and Repairing Structural Overspecification in Adaptive Data-Structure Selection
by: Alpay, Faruk, et al.
Published: (2026)

Formula Size-Depth Tradeoffs for Iterated Sub-Permutation Matrix Multiplication
by: Rossman, Benjamin
Published: (2024)

An SoS Entropy Dichotomy via Windowed Hypercontractivity
by: Lela, Marko
Published: (2025)

Completeness classes in algebraic complexity theory
by: Bürgisser, Peter
Published: (2024)

Curved Boolean Logic: A Contextual Generalization of Propositional Logic with Algorithmic Consequences
by: von Liechtenstein, Maximilian R. P.
Published: (2025)

A weak regularity lemma for polynomials
by: Moshkovitz, Guy, et al.
Published: (2025)

Regular Model Checking for Systems with Effectively Regular Reachability Relation
by: Esparza, Javier, et al.
Published: (2025)

Constraint Satisfaction Problems over Finitely Bounded Homogeneous Structures: a Dichotomy between FO and L-hard
by: Dorochko, Leonid, et al.
Published: (2026)

$Δ$-Nets: Interaction-Based System for Optimal Parallel $λ$-Reduction
by: Salvadori, Daniel Augusto Rizzi
Published: (2025)

Shifted Partial Derivative Polynomial Rank and Codimension
by: Edwards, Darren J.
Published: (2025)

Meta Theorem for Hardness on FCP-Problem
by: Nagao, Atsuki, et al.
Published: (2025)

Linear Matroid Intersection is in Catalytic Logspace
by: Agarwala, Aryan, et al.
Published: (2025)

Oracle Separations for RPH
by: Hamm, Thekla, et al.
Published: (2025)

Sign-Rank of $k$-Hamming Distance is Constant
by: Göös, Mika, et al.
Published: (2025)

A Note on Avoid vs MCSP
by: Hirsch, Edward A., et al.
Published: (2025)

Diagonalization Without Relativization A Closer Look at the Baker-Gill-Solovay Theorem
by: Garcia, Baruch
Published: (2026)

Required-edge Cycle Cover Problem: an ASP-Completeness Framework for Graph Problems and Puzzles
by: Susukita, Kosuke, et al.
Published: (2026)

Finitely (In)tractable Promise Constraint Satisfaction Problems
by: Asimi, Kristina, et al.
Published: (2020)