BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Date iCal//NONSGML kigkonsult.se iCalcreator 2.20.2//
METHOD:PUBLISH
X-WR-CALNAME;VALUE=TEXT:Ical
BEGIN:VTIMEZONE
TZID:Asia/Jerusalem
BEGIN:STANDARD
DTSTART:20181028T020000
TZOFFSETFROM:+0300
TZOFFSETTO:+0200
TZNAME:IST
END:STANDARD
BEGIN:DAYLIGHT
DTSTART:20180323T020000
TZOFFSETFROM:+0200
TZOFFSETTO:+0300
TZNAME:IDT
END:DAYLIGHT
END:VTIMEZONE
BEGIN:VEVENT
UID:calendar.58255.field_date.0@mathematics.huji.ac.il
DTSTAMP:20191020T030540Z
CREATED:20180530T230001Z
DESCRIPTION:Date: \n\n9:00am to 9:50am\n\n\n\n\nSee also: HD-Combinatoric
s\, Events & Seminars\, SeminarsLocation: \n\nFeldman Building\, Givat Ram
\n\n\n\nComputing R=P.Q \,the product of two mXm Boolean matrices [BMM] is
an ingredient\nof many combinatorial algorithms. \nMany efforts were made
to speed it beyond the standard m^3 steps\, without using\nthe algebraic
multiplication.\nTo divide the computation task\, encoding of the rows and
column indices were\nused (1.1) j by (j1\,j2) k by (k1\,k2)\ne.g. using i
nteger p j2=j mod p \,j1=ceiling of j/p.\n\nClearly\, the product of the r
anges of the digits= m1.m2 - is approximately m. \n L.Lee’s article reduce
d BMM to parsing substrings of a fixed string u with\nrespect to a context
-free grammar G. But the cubic complexity persisted. \n\n The reduction he
re is to a family of bi-graphs bunches\, each consisting of\ndirected grap
hs. The family is obtained from r distinct encodings (1.1) of\nthe indices
- and invoking the Chinese remainder theorem to produce the BMM R=P.Q.\n
If r is an integer\, e=1/r \,m2=m^(e) then the total number of steps is\n2
r.m^(2+e). E.g. if r=10 it is 20m^(2.1).\n This almost optimal BMM [and si
mple extensions] replaces the recourse to\ncomplicated algebraic matrix mu
ltiplications . It renders its improved\ncomplexity to graph property test
s which include BMM as a sub-routine: Finding \nall edges which belong to
triangles in a graph\, using it to reduce complexity\nof existence of k-cl
iques\, or edges in 4 vertex diamonds and some other\nsemi-cliques\; Findi
ng all pairs shortest walks in a graph and other applications: \n\nUsing V
aliant’s reduction of context-free parsing to \nBMM\, the complexity expon
ent three in standard parsing is reduced to 2+e with small e.\n\n Export
\n \n\n \nsubscribe iCal
DTSTART;TZID=Asia/Jerusalem:20180604T090000
DTEND;TZID=Asia/Jerusalem:20180604T095000
LAST-MODIFIED:20180530T230001Z
SUMMARY:HD-Combinatorics: Eli Shamir\, 'Almost optimal Boolean matrix multi
plication[BMM] - By Multi-encoding of rows and columns'
URL;TYPE=URI:https://mathematics.huji.ac.il/event/hd-combinatorics-eli-sham
ir-almost-optimal-boolean-matrix-multiplicationbmm-multi-encoding
END:VEVENT
END:VCALENDAR