Imagen de Portada

A nearly-$4\log n$ depth lower bound for formulas with restriction on top

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autor principal:	Wu, Hao
Formato:	Preprint
Publicado:	2024
Materias:	Computational Complexity
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

Complexity lower bounds for succinct binary structures of bounded clique-width with restrictions
por: Geniet, Colin, et al.
Publicado: (2026)

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

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

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

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

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

Anticoncentrated $n$-bit distribution from $\log(n)$ qubits
por: Zhang, Bingzhi, et al.
Publicado: (2025)

Quantum circuit lower bounds in the magic hierarchy
por: Parham, Natalie
Publicado: (2025)

On the consistency of stronger lower bounds for NEXP
por: Thapen, Neil
Publicado: (2025)

Searching for Falsified Clause in Random (log n)-CNFs is Hard for Randomized Communication
por: Riazanov, Artur, et al.
Publicado: (2025)

A quasi-optimal lower bound for skew polynomial multiplication
por: Chen, Qiyuan, et al.
Publicado: (2024)

PCF Learned Sort: a Learning Augmented Sort Algorithm with $O(n \log\log n)$ Expected Complexity
por: Sato, Atsuki, et al.
Publicado: (2024)

A note on quantum lower bounds for local search via congestion and expansion
por: Brânzei, Simina, et al.
Publicado: (2024)

An $Ω( (\log n / \log \log n)^2 )$ Cell-Probe Lower Bound for Dynamic Boolean Data Structures
por: Ko, Young Kun
Publicado: (2026)

Computational lower bounds for multi-frequency group synchronization
por: Kireeva, Anastasia, et al.
Publicado: (2024)

Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower bounds
por: Agarwal, Avantika, et al.
Publicado: (2024)

Query complexity lower bounds for local list-decoding and hard-core predicates (even for small rate and huge lists)
por: Ron-Zewi, Noga, et al.
Publicado: (2024)

Nine lower bound conjectures on streaming approximation algorithms for CSPs
por: Singer, Noah G.
Publicado: (2025)

Clifford testing: algorithms and lower bounds
por: Hinsche, Marcel, et al.
Publicado: (2025)

Conditional lower bounds for sparse parameterized 2-CSP: A streamlined proof
por: S., Karthik C., et al.
Publicado: (2023)

On complexity of restricted fragments of Decision DNNF
por: Calí, Andrea, et al.
Publicado: (2025)

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

SVP$_p$ is Deterministically NP-Hard for all $p > 2$, Even to Approximate Within a Factor of $2^{\log^{1-\varepsilon} n}$
por: Hair, Isaac M., et al.
Publicado: (2025)

On bounded depth proofs for Tseitin formulas on the grid; revisited
por: Håstad, Johan, et al.
Publicado: (2022)

Optimal lower bounds for quantum state tomography
por: Scharnhorst, Thilo, et al.
Publicado: (2025)

Rice-like complexity lower bounds for Boolean and uniform automata networks
por: Goubault-Larrecq, Aliénor, et al.
Publicado: (2024)

Refuting approaches to the log-rank conjecture for XOR functions
por: Hatami, Hamed, et al.
Publicado: (2023)

Efficient Isolation of Perfect Matching in O(log n) Genus Bipartite Graphs
por: Gupta, Chetan, et al.
Publicado: (2025)

A degree 4 sum-of-squares lower bound for the clique number of the Paley graph
por: Kunisky, Dmitriy, et al.
Publicado: (2022)

An unconditional lower bound for the active-set method on the hypercube
por: Disser, Yann, et al.
Publicado: (2025)

Unitary designs in nearly optimal depth
por: Cui, Laura, et al.
Publicado: (2025)

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

Quantum state testing with restricted measurements
por: Liu, Yuhan, et al.
Publicado: (2024)

Unconditionally separating noisy $\mathsf{QNC}^0$ from bounded polynomial threshold circuits of constant depth
por: Hsieh, Min-Hsiu, et al.
Publicado: (2024)

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

Negations are powerful even in small depth
por: Cavalar, Bruno, et al.
Publicado: (2025)

An unconditional lower bound for the active-set method in convex quadratic maximization
por: Bach, Eleon, et al.
Publicado: (2025)

Beyond Bell sampling: stabilizer state learning and quantum pseudorandomness lower bounds on qudits
por: Allcock, Jonathan, et al.
Publicado: (2024)

A near-optimal Quadratic Goldreich-Levin algorithm
por: Briët, Jop, et al.
Publicado: (2025)

#P-hardness proofs of matrix immanants evaluated on restricted matrices
por: Miklos, Istvan, et al.
Publicado: (2021)