Timeline for Will an integer program to deterministically factor integers help derandomize $\mathbb F_q[x]$ factoring?
Current License: CC BY-SA 4.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 6, 2023 at 13:22 | comment | added | Turbo | Non transfreability of the result of deterministic integer factoring through fixed dimension linear integer programming to the 'easier' problem of deterministic $\mathbb F_q[x]$ factoring could be a barrier to existence of such programs. | |
| Jan 6, 2023 at 13:15 | comment | added | Timothy Chow | Okay, so you think that proving that integer factorization is in $\mathsf{P}$ may be easier than proving that $\mathsf{P} = \mathsf{BPP}$. Fair enough. But your final comment still puzzles me. Did you mean to say that the transferability (rather than the non-transferability) would be a barrier? If problem $X$ seems hard and problem $Y$ seems easy, then a barrier to a proposed approach $A$ to solving $X$ might be that $A$ would allow $X$ to be reduced to $Y$, which we don't think can be done. | |
| Jan 6, 2023 at 4:30 | history | edited | Turbo | CC BY-SA 4.0 |
added 3 characters in body
|
| Jan 6, 2023 at 4:23 | history | edited | Turbo | CC BY-SA 4.0 |
added 914 characters in body
|
| Jan 6, 2023 at 4:18 | comment | added | Turbo | @TimothyChow Since my comment was going to be long I posted reply as an update to the MO post. | |
| Jan 6, 2023 at 4:17 | history | edited | Turbo | CC BY-SA 4.0 |
added 914 characters in body
|
| Jan 6, 2023 at 3:59 | comment | added | Timothy Chow | I don't quite understand the point of this question. If, in your quest for derandomization, you allow yourself to assume unproven hypotheses such as "integer factorization is in $\mathsf{P}$," then why not just assume the unproven hypothesis that $\mathsf{P} = \mathsf{BPP}$? Probably more people believe the latter than the former. | |
| Jan 6, 2023 at 3:03 | history | edited | Turbo | CC BY-SA 4.0 |
added 116 characters in body; edited tags
|
| Jan 5, 2023 at 12:58 | comment | added | Turbo | @BillBradley Just a statement of form $\exists x\in\mathbb Z^n: Ax\leq b$ is an integer program in $n$ dimensions. We take a particular variable, say $x_1$, and after the program is tested for solutions by Lenstra's algorithm compute $GCD(x_1,N)$ to get a possibly composite factor which is non-trivial. | |
| Jan 5, 2023 at 12:56 | history | edited | Turbo | CC BY-SA 4.0 |
added 59 characters in body
|
| Jan 5, 2023 at 12:51 | comment | added | Bill Bradley | Could you clarify what you mean by "without any objective function"? Isn't that usually part of the definition of an integer program? | |
| Jan 5, 2023 at 12:33 | history | asked | Turbo | CC BY-SA 4.0 |