Thesis Proposal: On Approximating by Polynomials and Several Related Models
Wed 12.07.22
1:30P EST | 3 Hour Event
Thesis Proposal: On Approximating by Polynomials and Several Related Models
Wed 12.07.22
1:30P EST
3 Hour Event
Wed 12.07.22
1:30P EST | 3 Hour Event
Wed 12.07.22
1:30P EST
3 Hour Event
Wed 12.07.22
1:30P EST | 3 Hour Event
Wed 12.07.22
1:30P EST
3 Hour Event
ABSTRACT:
We study the problem of approximating Boolean functions under two different notions of approximation, using three different but related models. 1. We consider the approximation to be point-wise, and we use real-valued polynomials to approximate. We study the degree in conjunction with the weight of such approximating polynomials. We show a tight approximate degree-weight result for any symmetric functions. We also show an approximate degree-weight result for bounded-width CNFs, and ‘’does not fool” theorem for symmetric functions on a relaxation of indistinguishability. Additionally, We reprove the following known approximate degree lower bounds in the language of indistinguishability. 2. We consider the approximation to be over uniform inputs, which coincides with the notion of average-case complexity. We use the model of AC0-Xor circuits, which are constant-depth circuits with a layer of parity gates (or their negations) at the bottom. We study the problem of approximating by such circuits via the perspective of affine extractors. We show that good affine extractors can be computed by small depth-4 AC0-Xor circuits, indicating that proving strong average-case lower bounds against such circuits are hard. We also show that one-sided affine extractors can be computed by small depth-3 AC0-Xor circuits, and separate these circuits from parity decision trees. 3. We again consider the same notion of approximation, and we use low-rank matrices to approximate. This is exactly the famous problem of constructing explicit rigid matrices. We construct matrices that are rigid even in the strong average-case. The main ingredients of the proof concern about point-wise approximating Boolean functions by linear combinations (with real coefficients) of functions from a simple class, which is the class of low-rank matrices here. Motivated by recent development of such ingredients, we will also explore (derandomized) direct products, selective XOR lemmas, and XOR lemmas for such approximate linear combinations.
ABOUT THE SPEAKER:
Xuangui Huang is a doctoral student at Northeastern University’s Khoury College of Computer Sciences, advised by Emanuele Viola. Xuangui is particularly interested in computational complexity. Prior to joining the doctoral program at Northeastern, Xuangui researched parameterized complexity, circuit complexity, and descriptive complexity while earning both his undergraduate and graduate degrees from Shanghai Jiao Tong University.
COMMITTEE:
LOCATION: 166 WVH
ABSTRACT:
We study the problem of approximating Boolean functions under two different notions of approximation, using three different but related models. 1. We consider the approximation to be point-wise, and we use real-valued polynomials to approximate. We study the degree in conjunction with the weight of such approximating polynomials. We show a tight approximate degree-weight result for any symmetric functions. We also show an approximate degree-weight result for bounded-width CNFs, and ‘’does not fool” theorem for symmetric functions on a relaxation of indistinguishability. Additionally, We reprove the following known approximate degree lower bounds in the language of indistinguishability. 2. We consider the approximation to be over uniform inputs, which coincides with the notion of average-case complexity. We use the model of AC0-Xor circuits, which are constant-depth circuits with a layer of parity gates (or their negations) at the bottom. We study the problem of approximating by such circuits via the perspective of affine extractors. We show that good affine extractors can be computed by small depth-4 AC0-Xor circuits, indicating that proving strong average-case lower bounds against such circuits are hard. We also show that one-sided affine extractors can be computed by small depth-3 AC0-Xor circuits, and separate these circuits from parity decision trees. 3. We again consider the same notion of approximation, and we use low-rank matrices to approximate. This is exactly the famous problem of constructing explicit rigid matrices. We construct matrices that are rigid even in the strong average-case. The main ingredients of the proof concern about point-wise approximating Boolean functions by linear combinations (with real coefficients) of functions from a simple class, which is the class of low-rank matrices here. Motivated by recent development of such ingredients, we will also explore (derandomized) direct products, selective XOR lemmas, and XOR lemmas for such approximate linear combinations.
ABOUT THE SPEAKER:
Xuangui Huang is a doctoral student at Northeastern University’s Khoury College of Computer Sciences, advised by Emanuele Viola. Xuangui is particularly interested in computational complexity. Prior to joining the doctoral program at Northeastern, Xuangui researched parameterized complexity, circuit complexity, and descriptive complexity while earning both his undergraduate and graduate degrees from Shanghai Jiao Tong University.
COMMITTEE:
LOCATION: 166 WVH
ABSTRACT:
We study the problem of approximating Boolean functions under two different notions of approximation, using three different but related models. 1. We consider the approximation to be point-wise, and we use real-valued polynomials to approximate. We study the degree in conjunction with the weight of such approximating polynomials. We show a tight approximate degree-weight result for any symmetric functions. We also show an approximate degree-weight result for bounded-width CNFs, and ‘’does not fool” theorem for symmetric functions on a relaxation of indistinguishability. Additionally, We reprove the following known approximate degree lower bounds in the language of indistinguishability. 2. We consider the approximation to be over uniform inputs, which coincides with the notion of average-case complexity. We use the model of AC0-Xor circuits, which are constant-depth circuits with a layer of parity gates (or their negations) at the bottom. We study the problem of approximating by such circuits via the perspective of affine extractors. We show that good affine extractors can be computed by small depth-4 AC0-Xor circuits, indicating that proving strong average-case lower bounds against such circuits are hard. We also show that one-sided affine extractors can be computed by small depth-3 AC0-Xor circuits, and separate these circuits from parity decision trees. 3. We again consider the same notion of approximation, and we use low-rank matrices to approximate. This is exactly the famous problem of constructing explicit rigid matrices. We construct matrices that are rigid even in the strong average-case. The main ingredients of the proof concern about point-wise approximating Boolean functions by linear combinations (with real coefficients) of functions from a simple class, which is the class of low-rank matrices here. Motivated by recent development of such ingredients, we will also explore (derandomized) direct products, selective XOR lemmas, and XOR lemmas for such approximate linear combinations.
ABOUT THE SPEAKER:
Xuangui Huang is a doctoral student at Northeastern University’s Khoury College of Computer Sciences, advised by Emanuele Viola. Xuangui is particularly interested in computational complexity. Prior to joining the doctoral program at Northeastern, Xuangui researched parameterized complexity, circuit complexity, and descriptive complexity while earning both his undergraduate and graduate degrees from Shanghai Jiao Tong University.
COMMITTEE:
LOCATION: 166 WVH
ABSTRACT:
We study the problem of approximating Boolean functions under two different notions of approximation, using three different but related models. 1. We consider the approximation to be point-wise, and we use real-valued polynomials to approximate. We study the degree in conjunction with the weight of such approximating polynomials. We show a tight approximate degree-weight result for any symmetric functions. We also show an approximate degree-weight result for bounded-width CNFs, and ‘’does not fool” theorem for symmetric functions on a relaxation of indistinguishability. Additionally, We reprove the following known approximate degree lower bounds in the language of indistinguishability. 2. We consider the approximation to be over uniform inputs, which coincides with the notion of average-case complexity. We use the model of AC0-Xor circuits, which are constant-depth circuits with a layer of parity gates (or their negations) at the bottom. We study the problem of approximating by such circuits via the perspective of affine extractors. We show that good affine extractors can be computed by small depth-4 AC0-Xor circuits, indicating that proving strong average-case lower bounds against such circuits are hard. We also show that one-sided affine extractors can be computed by small depth-3 AC0-Xor circuits, and separate these circuits from parity decision trees. 3. We again consider the same notion of approximation, and we use low-rank matrices to approximate. This is exactly the famous problem of constructing explicit rigid matrices. We construct matrices that are rigid even in the strong average-case. The main ingredients of the proof concern about point-wise approximating Boolean functions by linear combinations (with real coefficients) of functions from a simple class, which is the class of low-rank matrices here. Motivated by recent development of such ingredients, we will also explore (derandomized) direct products, selective XOR lemmas, and XOR lemmas for such approximate linear combinations.
ABOUT THE SPEAKER:
Xuangui Huang is a doctoral student at Northeastern University’s Khoury College of Computer Sciences, advised by Emanuele Viola. Xuangui is particularly interested in computational complexity. Prior to joining the doctoral program at Northeastern, Xuangui researched parameterized complexity, circuit complexity, and descriptive complexity while earning both his undergraduate and graduate degrees from Shanghai Jiao Tong University.
COMMITTEE:
LOCATION: 166 WVH