Xiaoyang Gu: Difference between revisions
Created page with "Title: Xiaoyang Gu Main Research Question: How can resource-bounded dimension theory be used to investigate polynomial size circuits? Methodology: The study uses resource-bounded measure and dimension, a powerful tool for examining the quantitative structure within complexity classes. It specifically focuses on the relationship between polynomial size circuits and uniform complexity classes. Results: The research shows that for every i≥0, P/polyi.o. has ith order sc..." |
No edit summary |
||
| Line 11: | Line 11: | ||
Additional Information: The study uses the equivalence between time-bounded Kolmogorov complexity KT and circuit-size complexity of strings to measure the class of polynomial size circuits more precisely. It also improves a recent result by Hitchcock and Vinodchandran [8] from dimension to scaled strong dimension by showing that for all i∈N, dim(i)p3(P/poly) = Dim(i)p3(P/poly) = 0. | Additional Information: The study uses the equivalence between time-bounded Kolmogorov complexity KT and circuit-size complexity of strings to measure the class of polynomial size circuits more precisely. It also improves a recent result by Hitchcock and Vinodchandran [8] from dimension to scaled strong dimension by showing that for all i∈N, dim(i)p3(P/poly) = Dim(i)p3(P/poly) = 0. | ||
Link to Article: https://arxiv.org/abs/ | Link to Article: https://arxiv.org/abs/0404044v2 | ||
Authors: | Authors: | ||
arXiv ID: | arXiv ID: 0404044v2 | ||
[[Category:Computer Science]] | [[Category:Computer Science]] | ||
Latest revision as of 15:50, 24 December 2023
Title: Xiaoyang Gu
Main Research Question: How can resource-bounded dimension theory be used to investigate polynomial size circuits?
Methodology: The study uses resource-bounded measure and dimension, a powerful tool for examining the quantitative structure within complexity classes. It specifically focuses on the relationship between polynomial size circuits and uniform complexity classes.
Results: The research shows that for every i≥0, P/polyi.o. has ith order scaled p3-strong dimension 0. It also demonstrates that P /polyi.o.has p3-dimension 1 /2, p3-strong dimension 1. These results improve previous measure results of Lutz (1992) and dimension results of Hitchcock and Vinodchandran (2004).
Implications: The findings provide valuable insights into the structure of polynomial size circuits, contributing to a deeper understanding of computational complexity. The improved measurement of P /polyi.o. using scaled dimensions and strong dimensions could lead to new techniques for analyzing and designing efficient circuits.
Additional Information: The study uses the equivalence between time-bounded Kolmogorov complexity KT and circuit-size complexity of strings to measure the class of polynomial size circuits more precisely. It also improves a recent result by Hitchcock and Vinodchandran [8] from dimension to scaled strong dimension by showing that for all i∈N, dim(i)p3(P/poly) = Dim(i)p3(P/poly) = 0.
Link to Article: https://arxiv.org/abs/0404044v2 Authors: arXiv ID: 0404044v2