Ich stimme zu, dass diese Seite Cookies verwende. Weitere Informationen finden Sie unter unseren Datenschutzerklärungen .
X
Göös, Mika
106  Ergebnisse:
Personensuche X
?
1

Separations in Proof Complexity and TFNP:

Göös, Mika ; Hollender, Alexandros ; Jain, Siddhartha...
Journal of the ACM.  71 (2024)  4 - p. 1-45 , 2024
Link: https://doi.org/10.1145/..
 
?
2

Depth-3 circuits for inner product:

Göös, Mika ; Guan, Ziyi ; Mosnoi, Tiberiu
Information and Computation.  300 (2024)  - p. 105192 , 2024
Link: https://doi.org/10.1016/..
 
?
3

Hardness Condensation by Restriction:

, In: Proceedings of the 56th Annual ACM Symposium on Theory of Computing,
Göös, Mika ; Newman, Ilan ; Riazanov, Artur. - p. 2016-2027 , 2024
Link: https://dl.acm.org/doi/1..
 
?
4

Further Collapses in \(\boldsymbol{\mathsf{TFNP}}\):

Göös, Mika ; Hollender, Alexandros ; Jain, Siddhartha...
SIAM Journal on Computing.  53 (2024)  3 - p. 573-587 , 2024
Link: https://doi.org/10.1137/..
 
?
5

Unambiguous DNFs and Alon–Saks–Seymour:

Balodis, Kaspars ; Ben-David, Shalev ; Göös, Mika..
SIAM Journal on Computing.  , 2023
Link: https://doi.org/10.1137/..
 
?
6

Top-Down Lower Bounds for Depth-Four Circuits:

, In: 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS),
Goos, Mika ; Riazanov, Artur ; Sofronova, Anastasia. - p. 1048-1055 , 2023
Link: https://doi.org/10.1109/..
 
?
7

Further collapses in TFNP:

, In: Proceedings of the 37th Computational Complexity Conference,
Göös, Mika ; Hollender, Alexandros ; Jain, Siddhartha... - p. 1-15 , 2022
Link: https://dl.acm.org/doi/1..
 
?
8

Randomised Composition and Small-Bias Minimax:

, In: 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS),
Ben-David, Shalev ; Blais, Eric ; Goos, Mika. - p. 624-635 , 2022
Link: https://doi.org/10.1109/..
 
?
9

Unambiguous DNFs and Alon-Saks-Seymour:

, In: 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS),
Balodis, Kaspars ; Ben-David, Shalev ; Goos, Mika.. - p. 116-124 , 2022
Link: https://doi.org/10.1109/..
 
?
10

Separations in Proof Complexity and TFNP:

, In: 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS),
Goos, Mika ; Hollender, Alexandros ; Jain, Siddhartha... - p. 1150-1161 , 2022
Link: https://doi.org/10.1109/..
 
?
11

Near-Optimal Communication Lower Bounds for Approximate Nas..:

Göös, Mika ; Rubinstein, Aviad
SIAM Journal on Computing.  52 (2021)  6 - p. FOCS18-316-FOCS18-348 , 2021
Link: https://doi.org/10.1137/..
 
?
12

Automating algebraic proof systems is NP-hard:

, In: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing,
de Rezende, Susanna F. ; Göös, Mika ; Nordström, Jakob... - p. 209-222 , 2021
Link: https://dl.acm.org/doi/1..
 
?
13

A majority lemma for randomised query complexity:

, In: Proceedings of the 36th Computational Complexity Conference,
Göös, Mika ; Maystre, Gilbert - p. 1 ff. , 2021
Link: https://dl.acm.org/doi/1..
 
?
14

On the power and limitations of branch and cut:

, In: Proceedings of the 36th Computational Complexity Conference,
Fleming, Noah ; Göös, Mika ; Impagliazzo, Russell... - p. 1 ff. , 2021
Link: https://dl.acm.org/doi/1..
 
?
15

On the complexity of modulo-q arguments and the chevalley-w..:

, In: Proceedings of the 35th Computational Complexity Conference,
Göös, Mika ; Kamath, Pritish ; Sotiraki, Katerina. - p. 1-42 , 2020
Link: https://dl.acm.org/doi/1..
 
1-15