I problemet med ORTHO GONAL VECTORS (OV) vill vi avgöra om det finns ett ortogonalt par vektorer bland n Booleska vektorer i d dimensioner. OV Conjecture (OVC) positerar att OV kräver n 2−o(1) tid att lösa, för alla d =  på (log n). Förutsatt att OVC, optimal tid lägre gränser har bevisats för många framträdande problem i P, såsom Redigera Avstånd, Frechet Avstånd, längst gemensamma Subsekvens, och approximering av diametern på en graf. Vi bevisar att OVC är sant i flera beräkningsmodeller av intresse: • För alla tillräckligt stora n och d, OV för n vektorer i {0, 1} d har förgrening program complexit en (n · min(n, 2 d )). I synnerhet de nedre gränserna matchar de övre gränserna upp till polylog faktorer. Trådar, i formler bestående av grindar som beräknar godtyckliga symmetriska funktioner hos obundna fläktar. Våra nedre gränser matchar i princip de mest kända (kvadratiska) nedre gränserna för alla explicita funktioner i dessa modeller. Analoga nedre gränser håller för många relaterade problem som visat sig vara svåra under OVC, såsom Batch Partial Match, Batch Subset Queries, och Batch Hamming Närmaste grannar, som alla har mycket kortfattade minskningar till OV. Bevisen använder en viss typ av inmatningsbegränsning som skiljer sig från typiska slumpmässiga begränsningar där variabler tilldelas självständigt. Vi ger en känsla av att oberoende slumpmässiga begränsningar inte kan användas för att visa hårdhet, i det att OVC är falskt i "genomsnittsfallet" även för AC 0 formler: • För varje fast p  till 0, 1) finns det en ε p > 0 sådan att för varje n och d, OV fall där ingångsbitar är självständigt satt till 1 med sannolikhet p (och 0 annars) kan lösas med AC 0 formler av storlek O (n 2-εp ), på alla utom en o n (1) bråkdel av fall. Dessutom, ε p → 1 som p → 1. * Stöds av en NSF CAREER.
Dessutom studerades OV hypotesen i begränsade modeller, såsom grenningsprogram REF.
The Orthogonal Vectors Conjecture for Branching Programs and Formulas
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}