Tata Institute of Fundamental Research
The power of regular and permutation branching programs
STCS Student Seminar
Speaker:
Hari Krishnan P A (TIFR)
Organiser:
Varun Ramanathan
Date:
Friday, 17 Nov 2023, 16:00 to 17:00
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
Branching programs are computational models which are similar to finite automata. They are particularly interesting because popular pseudorandom generators can fool certain classes of branching programs. In this talk, we will see a few restricted classes of branching programs, i.e., regular and permutation branching programs, and how effective they are in simulating other branching programs. All the results are taken from here: https://eccc.weizmann.ac.il/report/2023/102/
| Speaker: | Hari Krishnan P A (TIFR) |
| Organiser: | Varun Ramanathan |
| Date: | Friday, 17 Nov 2023, 16:00 to 17:00 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
Branching programs are computational models which are similar to finite automata. They are particularly interesting because popular pseudorandom generators can fool certain classes of branching programs. In this talk, we will see a few restricted classes of branching programs, i.e., regular and permutation branching programs, and how effective they are in simulating other branching programs. All the results are taken from here: https://eccc.weizmann.ac.il/report/2023/102/