BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260408T115748Z
UID:Seminar-dept-393@lxserverA.csc.liv.ac.uk.csc.liv.ac.uk
ORGANIZER:CN=Lutz Oettershagen:MAILTO:Lutz.Oettershagen@liverpool.ac.uk
DTSTART:20151027T130000
DTEND:20151027T140000
SUMMARY:School Seminar Series
DESCRIPTION:Dr Oded Lachish: Trading query complexity for sample-based testing and multi-testing scalability\n\nWe show that every non-adaptive property testing algorithm making a constant number of queries, over a fixed alphabet, can be converted to a sample-based (as per [Goldreich and Ron, 2015]) testing algorithm whose average number of queries is a fixed, smaller than $1$, power of $n$. Since the query distribution of the sample-based algorithm is not dependent at all on the property, or the original algorithm, this has many implications in scenarios where there are many properties that need to be tested for concurrently, such as testing (relatively large) unions of properties, or converting a Merlin-Arthur Proximity proof (as per [Gur and Rothblum, 2013]) to a proper testing algorithm.\n\n\n\nThe proof method involves preparing the original testing algorithm for a combinatorial analysis. For the analysis we develop a structural lemma for hypergraphs that may be of independent interest. When analyzing a hypergraph that was extracted from a $2$-sided test, it allows for finding generalized sunflowers that provide for a large-deviation type analysis. For $1$-sided tests the bounds can be improved further by applying Janson's inequality directly over our structures.\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=393
LOCATION:Ashton Lecture Theater
END:VEVENT
END:VCALENDAR