- Testing a start in a graph
- Project Year:
2024
- REU Student (s):
Ben Bencik | Charles University (Prague, Czech Republic)
- Student 1 Institution:
Charles University (Prague, Czech Republic)
- Project Mentor:
Sumegha Garg
- Project Mentor Area:
Computer Science
- Project Abstract:
Property testing is a notion of approximation for decision problems, where given a property, the task is to distinguish whether a given instance has this property or is "far" from any instance having the property. A key complexity measure for property testing algorithms is its query complexity, which is the maximum number of input elements queried to determine whether the graph satisfies a given property. While there are established bounds for the query complexity of various graph properties, there are hardly any results on the impact of memory constraints. This project investigates property testing on graphs, studying how memory constraints affect the complexity of property testing in both deterministic models and scenarios involving random queries.
