Copertina

Are Depth-2 Regular Expressions Hard to Intersect?

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Ascone, Rocco, Bernardini, Giulia, Conte, Alessio, Guerrini, Veronica, Punzi, Giulia
Natura:	Preprint
Pubblicazione:	2025
Soggetti:	Computational Complexity
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

The Complexity of Maximal Common Subsequence Enumeration
di: Buzzega, Giovanni, et al.
Pubblicazione: (2025)

On the Hardness of Learning Regular Expressions
di: Attias, Idan, et al.
Pubblicazione: (2025)

Forrelation is Extremally Hard
di: Girish, Uma, et al.
Pubblicazione: (2025)

Hardness of Regular Expression Matching with Extensions
di: Nogami, Taisei, et al.
Pubblicazione: (2026)

Improved Hardness Results for Learning Intersections of Halfspaces
di: Tiegel, Stefan
Pubblicazione: (2024)

Testing Sumsets is Hard
di: Chen, Xi, et al.
Pubblicazione: (2024)

Finding Diverse Strings and Longest Common Subsequences in a Graph
di: Shida, Yuto, et al.
Pubblicazione: (2024)

Randomized Black-Box PIT for Small Depth +-Regular Non-commutative Circuits
di: Bharadwaj, G V Sumukha, et al.
Pubblicazione: (2024)

AC^0[p]-Frege Cannot Efficiently Prove that Constant-Depth Algebraic Circuit Lower Bounds are Hard
di: Lu, Jiaqi, et al.
Pubblicazione: (2025)

Asymptotically Optimal Hardness for $k$-Set Packing and $k$-Matroid Intersection
di: Lee, Euiwoong, et al.
Pubblicazione: (2024)

Reasoning About Knowledge on Regular Expressions is 2EXPTIME-complete
di: Ghosh, Avijeet, et al.
Pubblicazione: (2025)

On the NP-Hardness Approximation Curve for Max-2Lin(2)
di: Martinsson, Björn
Pubblicazione: (2024)

Inverse Intersections for Boolean Satisfiability Problems
di: Homer, Paul W.
Pubblicazione: (2025)

Maximizing Minimum Cycle Bases Intersection
di: Watel, Dimitri, et al.
Pubblicazione: (2024)

Regular Expressions with Backreferences and Lookaheads Capture NLOG
di: Uezato, Yuya
Pubblicazione: (2024)

Carrying is Hard: Exploring the Gap between Hardness for NP and PSPACE for the Hanano and Jelly no Puzzles
di: Chavrimootoo, Michael C., et al.
Pubblicazione: (2026)

Hardness of SetCover Reoptimization
di: Jansen, Klaus, et al.
Pubblicazione: (2025)

On the Hardness of the Drone Delivery Problem
di: Bartlmae, Simon, et al.
Pubblicazione: (2025)

PSPACE-Hard 2D Super Mario Games: Thirteen Doors
di: MIT Hardness Group, et al.
Pubblicazione: (2024)

Hardness of clique approximation for monotone circuits
di: Błasiok, Jarosław, et al.
Pubblicazione: (2025)

Bounds for Hardness Condensation in the Query Model
di: Kayal, Chandrima, et al.
Pubblicazione: (2026)

Hardness Amplification via Group Theory
di: Nareddy, Tejas, et al.
Pubblicazione: (2024)

Near Optimal Hardness of Approximating $k$-CSP
di: Minzer, Dor, et al.
Pubblicazione: (2025)

On the Hardness of Order Finding and Equivalence Testing for ROABPs
di: Ramya, C., et al.
Pubblicazione: (2025)

Higher Hardness Results for the Reconfiguration of Odd Matchings
di: Dorfer, Joseph
Pubblicazione: (2026)

Hard-to-Sample Distributions from Robust Extractors
di: Byramji, Farzan, et al.
Pubblicazione: (2026)

Tetris is Hard with Just One Piece Type
di: MIT Hardness Group, et al.
Pubblicazione: (2026)

Hard CNF Instances for Ideal Proof Systems
di: Hakoniemi, Tuomas, et al.
Pubblicazione: (2026)

Compression of Voxelized Vector Field Data by Boxes is Hard
di: Zhang, Simon
Pubblicazione: (2025)

New Techniques for Constructing Rare-Case Hard Functions
di: Nareddy, Tejas, et al.
Pubblicazione: (2024)

Optimal Proof Systems for Complex Sets are Hard to Find
di: Egidy, Fabian, et al.
Pubblicazione: (2024)

On the Hardness of Finding Temporally Connected Subgraphs of Any Size
di: Casteigts, Arnaud, et al.
Pubblicazione: (2026)

Hardness of Random Reordered Encodings of Parity for Resolution and CDCL
di: Chew, Leroy, et al.
Pubblicazione: (2024)

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

Worst-Case and Average-Case Hardness of Hypercycle and Database Problems
di: Fu, Cheng-Hao, et al.
Pubblicazione: (2025)

PCP-free APX-Hardness of Nearest Codeword and Minimum Distance
di: Bhattiprolu, Vijay, et al.
Pubblicazione: (2025)

Hardness of Hypergraph Edge Modification Problems
di: Gishboliner, Lior, et al.
Pubblicazione: (2025)

Low Rank Matrix Rigidity: Tight Lower Bounds and Hardness Amplification
di: Alman, Josh, et al.
Pubblicazione: (2025)

Towards Solving NP-Complete and Other Hard Problems Efficiently in Practice
di: Digulescu, Mircea-Adrian
Pubblicazione: (2026)

Average-Case Hardness of Binary-Encoded Clique in Proof and Communication Complexity
di: de Rezende, Susanna F., et al.
Pubblicazione: (2026)