-
[J28]
-
Y. Hamoudi and F. Magniez. Quantum Time-Space Tradeoff for Finding
Multiple Collision Pairs. In: ACM Transactions on Computation Theory 15.1-2
(2023). doi: 10.1145/3589986.
-
[J27]
-
F. Magniez and A. Nayak. Quantum Distributed Complexity of Set Disjointness
on a Line. In: ACM Transactions on Computation Theory 14.1 (2022), pp. 1–22.
doi: 10.1145/3512751.
-
[J26]
-
T. Carette, M. Laurière, and F. Magniez. Extended Learning Graphs
for Triangle Finding. In: Algorithmica 82 (2020), pp. 980–1005. doi:
10.1007/s00453-019-00627-z.
-
[J25]
-
L. Boczkowski, I. Kerenidis, and F. Magniez. Streaming Communication
Protocols. In: ACM Transactions on Computation Theory 10.4 (2018),
19:1–19:21. doi: 10.1145/3276748.
-
[J24]
-
S. Jeffery, F. Magniez, and
R. de Wolf. Optimal parallel quantum query algorithms. In: Algorithmica 79.2
(2017), pp. 509–529. doi: 10.1007/s00453-016-0206-z.
-
[J23]
-
T. Lee, F. Magniez, and M. Santha. Improved quantum query algorithms
for triangle finding and associativity testing. In: Algorithmica 77.2 (2017),
pp. 459–486. doi: 10.1007/s00453-015-0084-9.
-
[J22]
-
S. Jeffery, R. Kothari, F. Le Gall, and F. Magniez. Improving Quantum
Query Complexity of Boolean Matrix Multiplication Using Graph Collision. In:
Algorithmica 76.1 (2016), pp. 1–16. doi: 10.1007/s00453-015-9985-x.
-
[J21]
-
H. Krovi, F. Magniez, M. Ozols, and J. Roland. Quantum walks can find a
marked element on any graph. In: Algorithmica 74.2 (2016), pp. 851–907. doi:
10.1007/s00453-015-9979-8.
-
[J20]
-
F. Magniez, A. Nayak, M. Santha, J. Sherman, G. Tardos, and D. Xiao.
Improved bounds for the randomized decision tree complexity of recursive
majority. In: Random Structures & Algorithms 48.3 (2016), pp. 612–638. doi:
10.1002/rsa.20598.
-
[J19]
-
K. Friedl, G. Ivanyos, F. Magniez, M. Santha, and P. Sen. Hidden translation
and orbit coset in quantum computing. In: SIAM Journal on Computing 43.1
(2014), pp. 1–24. doi: 10.1137/130907203.
-
[J18]
-
F. Magniez, C. Mathieu, and A. Nayak. Recognizing well-parenthesized
expressions in the streaming model. In: SIAM Journal on Computing 43 (6 2014),
pp. 1880–1905. doi: 10.1137/130926122.
-
[J17]
-
C. Konrad and F. Magniez. Validating XML documents in the streaming model
with external memory. In: ACM Transactions on Database Systems 38.4 (2013).
Special issue of ICDT’12, p. 27. doi: 10.1145/2504590.
-
[J16]
-
T. Lee, F. Magniez, and M. Santha. A learning graph based quantum query
algorithm for finding constant-size subgraphs. In: Chicago Journal of Theoretical
Computer Science 10 (2012). doi: 10.4086/cjtcs.2012.010.
-
[J15]
-
F. Magniez, A. Nayak, P. Richter, and M. Santha. On the hitting times of
quantum versus random walks. In: Algorithmica 63.1 (2012), pp. 91–116. doi:
10.1007/s00453-011-9521-6.
-
[J14]
-
F. Magniez, A. Nayak, J. Roland, and M. Santha. Search via quantum walk. In:
SIAM Journal on Computing 40.1 (2011), pp. 142–164. doi: 10.1137/090745854.
-
[J13]
-
E. Fischer, F. Magniez, and M. de Rougemont. Approximate satisfiability and
equivalence. In: SIAM Journal on Computing 39.6 (2010), pp. 2251–2281. doi:
10.1137/070703776.
-
[J12]
-
L. Magnin, F. Magniez, A. Leverrier, and N. Cerf. Strong no-go theorem for
gaussian quantum bit commitment. In: Physical Review A 81.1 (2010), 010302(R).
doi: 10.1103/PhysRevA.81.010302.
-
[J11]
-
K. Friedl, F. Magniez, M. Santha, and P. Sen. Quantum testers for hidden group
properties. In: Fundamenta Matematicae 91.2 (2009). Special issue on Machines
on Computations and Universality, pp. 325–340. doi: 10.3233/FI-2009-0046.
-
[J10]
-
S. Laplante and F. Magniez. Lower bounds for randomized and quantum query
complexity using Kolmogorov arguments. In: SIAM Journal on Computing 38.1
(2008), pp. 46–62. doi: 10.1137/050639090.
-
[J9]
-
W. van Dam, F. Magniez, M. Mosca, and M. Santha. Self-testing of universal
and fault-tolerant sets of quantum gates. In: SIAM Journal on Computing 37.2
(2007), pp. 611–629. doi: 10.1137/S0097539702404377.
-
[J8]
-
S. Laplante, R. Lassaigne, F. Magniez, S. Peyronnet, and M. de Rougemont.
Probabilistic abstraction for model checking: An approach based on property
testing. In: ACM Transactions on Computational Logic 8.4 (2007), p. 20. doi:
10.1145/1276920.1276922.
-
[J7]
-
F. Magniez and A. Nayak. Quantum complexity of testing group commutativity.
In: Algorithmica 48.3 (2007), pp. 221–232. doi: 10.1007/s00453-007-0057-8.
-
[J6]
-
F. Magniez and M. de Rougemont. Property testing of regular tree languages.
In: Algorithmica 49.2 (2007), pp. 127–146. doi: 10.1007/s00453-007-9028-3.
-
[J5]
-
F. Magniez, M. Santha, and M. Szegedy. Quantum algorithms for the triangle
problem. In: SIAM Journal on Computing 37.2 (2007), pp. 413–424. doi:
10.1137/050643684.
-
[J4]
-
H. Buhrman, C. Dürr, M. Heiligman, P. Høyer, F. Magniez, M. Santha, and R.
de Wolf. Quantum algorithms for element distinctness. In: SIAM Journal on
Computing 34.6 (2005), pp. 1324–1330. doi: 10.1137/S0097539702402780.
-
[J3]
-
F. Magniez. Multi-linearity self-testing with relative error. In: Theory of
Computing Systems 38.5 (2005), pp. 573–591. doi: 10.1007/s00224-004-1125-y.
-
[J2]
-
G. Ivanyos, F. Magniez, and M. Santha. Efficient quantum algorithms for
some instances of the non-Abelian hidden subgroup problem. In: International
Journal of Foundations of Computer Science 14.5 (2003), pp. 723–740. doi:
10.1142/S0129054103001996.
-
[J1]
-
M. Kiwi, F. Magniez, and M. Santha. Approximate testing with error relative
to input size. In: Journal of Computer and System Sciences 66.2 (2003),
pp. 371–392. doi: 10.1016/S0022-0000(03)00004-7.
-
[P40]
-
P. Fraigniaud, M. Luce, F. Magniez, and I. Todinca. Even-Cycle Detection in
the Randomized and Quantum CONGEST Model. In: Proceedings of 43rd ACM
Symposium on Principles of Distributed Computing. 2024, pp. 209–219. doi:
10.1145/3662158.3662767.
-
[P39]
-
Y. Hamoudi and F. Magniez. Quantum Time-Space Tradeoff for Finding
Multiple Collision Pairs. In: Proceedings of 16th Conference on the Theory of
Quantum Computation, Communication and Cryptography. TQC Outstanding
Paper Prize. 2021, 1:1–1:21. doi: 10.4230/LIPIcs.TQC.2021.1.
-
[P38]
-
T. Izumi, F. Le Gall, and F. Magniez. Quantum Distributed Algorithm for
Triangle Finding in the CONGEST Model. In: Proceedings of 37th International
Symposium on Theoretical Aspects of Computer Science. Also presented at
TQC’20. 2020, 23:1–23:13. doi: 10.4230/LIPIcs.STACS.2020.23.
-
[P37]
-
F. Magniez and A. Nayak. Quantum Distributed Complexity of Set Disjointness
on a
Line. In: Proceedings of 47th International Colloquium on Automata, Languages
and Programming. 82:1–82:18. 2020. doi: 10.4230/LIPIcs.ICALP.2020.82.
-
[P36]
-
Y. Hamoudi and F. Magniez. Quantum Chebyshev’s Inequality and Applications.
In: Proceedings of 46th International Colloquium on Automata, Languages and
Programming. 2019, 69:1–69:16. doi: 10.4230/LIPIcs.ICALP.2019.69.
-
[P35]
-
E. Fischer, F. Magniez, and T. Starikovskaya. Improved bounds for testing
Dyck languages. In: Proceedings of 29th ACM-SIAM Symposium on Discrete
Algorithms. 2018, pp. 1529–1544. doi: 10.1137/1.9781611975031.100.
-
[P34]
-
F. Le Gall and F. Magniez. Sublinear-Time Quantum Computation of the
Diameter in CONGEST Networks. In: Proceedings of 37th ACM Symposium on
Principles of Distributed Computing. Also presented at QIP’19 as a contributed
talk. 2018, pp. 337–346. doi: 10.1145/3212734.3212744.
-
[P33]
-
L.
Boczkowski, I. Kerenidis, and F. Magniez. Streaming Communication Protocols.
In: Proceedings of 44th International Colloquium on Automata, Languages, and
Programming. 2017, 130:1–130:14. doi: 10.4230/LIPIcs.ICALP.2017.130.
-
[P32]
-
T. Carette, M. Laurière, and F. Magniez. Extended Learning Graphs for Triangle
Finding. In: Proceedings of 34th International Symposium on Theoretical Aspects
of Computer Science. 2017, 20:1–20:14. doi: 10.4230/LIPIcs.STACS.2017.20.
-
[P31]
-
N. François, F. Magniez, M. de Rougemont, and O. Serre. Streaming Property
Testing of Visibly Pushdown Languages. In: Proceedings of 24rd European
Symposium on Algorithms. 2016, 43:1–43:17. doi: 10.4230/LIPIcs.ESA.2016.43.
-
[P30]
-
V. Kanade, N. Leonardos, and
F. Magniez. Stable Matching with Evolving Preferences. In: Proceedings of 20th
International Workshop on Randomization and Computation. 2016, 36:1–36:13.
doi: 10.4230/LIPIcs.APPROX-RANDOM.2016.36.
-
[P29]
-
N. François, R. Jain, and F. Magniez. Unidirectional Input/Output Streaming
Complexity of Reversal and Sorting. In: Proceedings of 18th International
Workshop on Randomization and Computation. 2014, pp. 654–668. doi:
10.4230/LIPIcs.APPROX-RANDOM.2014.654.
-
[P28]
-
S. Jeffery, F. Magniez, and R. de Wolf. Optimal parallel quantum query
algorithms. In: Proceedings of 22nd European Symposium on Algorithms. 2014,
pp. 592–604. doi: 10.1007/978-3-662-44777-2_49.
-
[P27]
-
A. Belovs, A. Childs, S. Jeffery, R. Kothari, and F. Magniez. Time-Efficient
Quantum Walks for 3-Distinctness. In: Proceedings of 40th International
Colloquium on Automata, Languages and Programming. Also presented at QIP’14
as a contributed talk. 2013, pp. 105–122. doi: 10.1007/978-3-642-39206-1_10.
-
[P26]
-
N. François and F. Magniez. Streaming complexity of checking priority queues.
In: Proceedings of 30th Symposium on Theoretical Aspects of Computer Science.
2013, pp. 454–465. doi: 10.4230/LIPIcs.STACS.2013.454.
-
[P25]
-
S. Jeffery, R. Kothari, and F. Magniez. Nested quantum walks with quantum
data structures. In: Proceedings of 24th ACM-SIAM Symposium on Discrete
Algorithms. Also presented at QIP’14 as a contributed talk. 2013, pp. 1474–1485.
doi: 10.1137/1.9781611973105.106.
-
[P24]
-
T. Lee, F. Magniez, and M. Santha. Improved quantum query algorithms for
triangle finding and associativity testing. In: Proceedings of 24th ACM-SIAM
Symposium on Discrete Algorithms. Also presented at QIP’13 as a contributed
talk. 2013, pp. 1486–1502. doi: 10.1137/1.9781611973105.107.
-
[P23]
-
S. Jeffery, R. Kothari, and F. Magniez. Improving quantum query complexity
of boolean matrix multiplication using graph collision. In: Proceedings of 39th
International Colloquium on Automata, Languages and Programming. 2012,
pp. 522–532. doi: 10.1007/978-3-642-31594-7_44.
-
[P22]
-
C. Konrad and
F. Magniez. Validating XML documents in the streaming model with external
memory. In: Proceedings of 15th International Conference on Database Theory.
Best Newcomer Paper. 2012, pp. 34–45. doi: 10.1145/2274576.2274581.
-
[P21]
-
C. Konrad, F. Magniez, and C. Mathieu. Maximum matching in
semi-streaming with few passes. In: Proceedings of 15th International Workshop
on Approximation Algorithms for Combinatorial Optimization Problems. Full
version on arXiv. 2012, pp. 231–242. doi: 10.1007/978-3-642-32512-0_20. arXiv:
1112.0184.
-
[P20]
-
F. Magniez, A. Nayak, M. Santha, and D. Xiao. Improved bounds for the
randomized decision tree complexity of recursive majority. In: Proceedings of
38th International Colloquium on Automata, Languages and Programming. 2011,
pp. 317–329. doi: 10.1007/978-3-642-22006-7_27.
-
[P19]
-
F. Magniez, M. de Rougemont, M. Santha, and X. Zeitoun. The complexity
of approximate Nash equilibrium in congestion games with negative delays.
In: Proceedings of 7th Workshop on Internet & Network Economics. 2011,
pp. 266–277. doi: 10.1007/978-3-642-25510-6_23.
-
[P18]
-
H. Krovi, F. Magniez, M. Ozols, and J. Roland. Finding is as easy as detecting for
quantum walks. In: Proceedings of 37th International Colloquium on Automata,
Languages and Programming. Also presented at QIP’11 as a featured talk. 2010,
pp. 540–551. doi: 10.1007/978-3-642-14165-2_46.
-
[P17]
-
F. Magniez, C. Mathieu, and A. Nayak. Recognizing well-parenthesized
expressions in the streaming model. In: Proceedings of 42nd ACM Symposium on
Theory of Computing. 2010, pp. 261–270. doi: 10.1145/1806689.1806727.
-
[P16]
-
F. Magniez, A. Nayak, P. Richter, and M. Santha. On the hitting times of
quantum versus random walks. In: Proceedings of 20th ACM-SIAM Symposium
on Discrete Algorithms. 2009, pp. 86–95. doi: 10.1137/1.9781611973068.10.
-
[P15]
-
F. Magniez, A. Nayak, J. Roland, and M. Santha. Search via quantum walk. In:
Proceedings of 39th ACM Symposium on Theory of Computing. Also presented at
QIP’07 as a contributed talk. 2007, pp. 575–584. doi: 10.1145/1250790.1250874.
-
[P14]
-
E. Fischer, F. Magniez, and M. de Rougemont. Approximate satisfiability and
equivalence. In: Proceedings of 21st IEEE Symposium on Logic in Computer
Science. 2006, pp. 421–430. doi: 10.1109/LICS.2006.12.
-
[P13]
-
F. Magniez, D. Mayers, M. Mosca, and H. Ollivier. Self-testing of quantum
circuits. In: Proceedings of 33rd International Colloquium on Automata,
Languages and Programming. Also presented at QIP’06 as a contributed talk.
2006, pp. 72–83. doi: 10.1007/11786986_8.
-
[P12]
-
F. Magniez and A. Nayak. Quantum complexity of testing group commutativity.
In: Proceedings of 32nd International Colloquium on Automata, Languages and
Programming. 2005, pp. 1312–1324. doi: 10.1007/11523468_106.
-
[P11]
-
F. Magniez, M. Santha, and M. Szegedy. Quantum algorithms for the triangle
problem. In: Proceedings of 16th ACM-SIAM Symposium on Discrete Algorithms.
Also presented at QIP’04 as an invited talk. 2005, pp. 1109–1117.
-
[P10]
-
S. Laplante and F. Magniez. Lower bounds for randomized and quantum
query complexity using Kolmogorov arguments. In: Proceedings of 19th
IEEE Conference on Computational Complexity. 2004, pp. 214–304. doi:
10.1109/CCC.2004.1313852.
-
[P9]
-
F. Magniez and M. de Rougemont. Property testing of regular tree languages.
In: Proceedings of 31st International Colloquium on Automata, Languages and
Programming. 2004, pp. 932–944. doi: 10.1109/LICS.2006.12.
-
[P8]
-
K. Friedl, G. Ivanyos, F. Magniez, M. Santha, and P. Sen. Hidden translation and
orbit coset in quantum computing. In: Proceedings of 35th ACM Symposium on
Theory of Computing. Also presented at QIP’03 as an invited talk. 2003, pp. 1–9.
doi: 10.1145/780542.780544.
-
[P7]
-
K. Friedl, F. Magniez, M. Santha, and P. Sen. Quantum testers for
hidden group properties. In: Proceedings of the 28th International Symposium
on Mathematical Foundations of Computer Science. 2003, pp. 419–428. doi:
10.1007/978-3-540-45138-9_36.
-
[P6]
-
S. Laplante, R. Lassaigne, F. Magniez, S. Peyronnet, and M. de Rougemont.
Probabilistic abstraction for model checking: An approach based on property
testing. In: Proceedings of 17th IEEE Symposium on Logic in Computer Science.
2002, pp. 30–39. doi: 10.1109/LICS.2002.1029815.
-
[P5]
-
H. Buhrman, C. Dürr, M. Heiligman, P. Høyer, F. Magniez, M. Santha, and
R. de Wolf. Quantum algorithms for element distinctness. In: Proceedings of
15th IEEE Conference on Computational Complexity. 2001, pp. 131–137. doi:
10.1109/CCC.2001.933880.
-
[P4]
-
G. Ivanyos, F. Magniez, and M. Santha. Efficient quantum algorithms for
some instances of the non-Abelian hidden subgroup problem. In: Proceedings
of 13th ACM Symposium on Parallelism in Algorithms and Architectures. 2001,
pp. 263–270. doi: 10.1145/378580.378679.
-
[P3]
-
W. van Dam, F. Magniez, M. Mosca, and M. Santha. Self-testing of universal and
fault-tolerant sets of quantum gates. In: Proceedings of 32nd ACM Symposium
on Theory of Computing. 2000, pp. 688–696. doi: 10.1145/335305.335402.
-
[P2]
-
F. Magniez. Multi-linearity self-testing with relative error. In: Proceedings of
17th Symposium on Theoretical Aspects of Computer Science. 2000, pp. 302–313.
doi: 10.1007/3-540-46541-3_25.
-
[P1]
-
M. Kiwi, F. Magniez, and M. Santha. Approximate testing with relative error. In:
Proceedings of 31st ACM Symposium on Theory of Computing. 1999, pp. 51–60.
doi: 10.1145/301250.301269.