Recent

Refereed Articles
[2017] Improved quantum query algorithms for triangle finding and associativity testing (T. Lee, F. Magniez, M. Santha), In Algorithmica, volume 77, 2017. [bib] [pdf]
[2016] Improved bounds for the randomized decision tree complexity of recursive majority (F. Magniez, A. Nayak, M. Santha, J. Sherman, G. Tardos, D. Xiao), In Random Structures & Algorithms, volume 48, 2016. [bib] [pdf]
[2016] Quantum walks can find a marked element on any graph (H. Krovi, F. Magniez, M. Ozols, J. Roland), In Algorithmica, volume 74, 2016. [bib] [pdf]
[2016] Optimal parallel quantum query algorithms (S. Jeffery, F. Magniez, R. de Wolf), In Algorithmica, 2016. (To appear) [bib] [pdf]
[2016] Improving Quantum Query Complexity of Boolean Matrix Multiplication Using Graph Collision (S. Jeffery, R. Kothari, F. Le Gall, F. Magniez), In Algorithmica, volume 76, 2016. [bib] [pdf]
Refereed Conference Papers
[2017] Extended Learning Graphs for Triangle Finding (T. Carette, M. Laurière, F. Magniez), In Proceedings of 34th International Symposium on Theoretical Aspects of Computer Science, 2017. [bib] [pdf]
[2017] Streaming Communication Protocols (L. Boczkowski, I. Kerenidis, F. Magniez), In Proceedings of 44th International Colloquium on Automata, Languages, and Programming, 2017. (To appear) [bib] [pdf]
[2016] Stable Matching with Evolving Preferences (V. Kanade, N. Leonardos, F. Magniez), In Proceedings of 20th International Workshop on Randomization and Computation, 2016. [bib] [pdf]
[2016] Streaming Property Testing of Visibly Pushdown Languages (N. François, F. Magniez, M. de Rougemont, O. Serre), In Proceedings of 24rd European Symposium on Algorithms, 2016. [bib] [pdf]
Other Publications
[2017] Improved bounds for testing Dyck languages (E. Fischer, F. Magniez, T. Starikovskaya), Technical report, arXiv.org, 2017. [bib] [url] [pdf]
Powered by bibtexbrowser

All

Refereed Articles
[2017] Improved quantum query algorithms for triangle finding and associativity testing (T. Lee, F. Magniez, M. Santha), In Algorithmica, volume 77, 2017. [bib] [pdf]
[2016] Improved bounds for the randomized decision tree complexity of recursive majority (F. Magniez, A. Nayak, M. Santha, J. Sherman, G. Tardos, D. Xiao), In Random Structures & Algorithms, volume 48, 2016. [bib] [pdf]
[2016] Quantum walks can find a marked element on any graph (H. Krovi, F. Magniez, M. Ozols, J. Roland), In Algorithmica, volume 74, 2016. [bib] [pdf]
[2016] Optimal parallel quantum query algorithms (S. Jeffery, F. Magniez, R. de Wolf), In Algorithmica, 2016. (To appear) [bib] [pdf]
[2016] Improving Quantum Query Complexity of Boolean Matrix Multiplication Using Graph Collision (S. Jeffery, R. Kothari, F. Le Gall, F. Magniez), In Algorithmica, volume 76, 2016. [bib] [pdf]
[2014] Recognizing well-parenthesized expressions in the streaming model (F. Magniez, C. Mathieu, A. Nayak), In SIAM Journal on Computing, volume 43, 2014. [bib] [pdf]
[2014] Hidden translation and orbit coset in quantum computing (K. Friedl, G. Ivanyos, F. Magniez, M. Santha, P. Sen), In SIAM Journal on Computing, volume 43, 2014. [bib] [pdf]
[2013] Validating XML documents in the streaming model with external memory (C. Konrad, F. Magniez), In ACM Transactions on Database Systems, volume 38, 2013. (Special issue of ICDT'12) [bib] [pdf]
[2012] On the hitting times of quantum versus random walks (F. Magniez, A. Nayak, P. Richter, M. Santha), In Algorithmica, volume 63, 2012. [bib] [pdf]
[2012] A learning graph based quantum query algorithm for finding constant-size subgraphs (T. Lee, F. Magniez, M. Santha), In Chicago Journal of Theoretical Computer Science, 2012. [bib] [pdf]
[2011] Search via quantum walk (F. Magniez, A. Nayak, J. Roland, M. Santha), In SIAM Journal on Computing, volume 40, 2011. [bib] [pdf]
[2010] Strong no-go theorem for gaussian quantum bit commitment (L. Magnin, F. Magniez, A. Leverrier, N. Cerf), In Physical Review A, volume 81, 2010. [bib] [pdf]
[2010] Approximate satisfiability and equivalence (E. Fischer, F. Magniez, M. de Rougemont), In SIAM Journal on Computing, volume 39, 2010. [bib] [pdf]
[2009] Quantum testers for hidden group properties (K. Friedl, F. Magniez, M. Santha, P. Sen), In Fundamenta Matematicae, volume 91, 2009. (Special issue on Machines on Computations and Universality) [bib] [pdf]
[2008] Lower bounds for randomized and quantum query complexity using Kolmogorov arguments (S. Laplante, F. Magniez), In SIAM Journal on Computing, volume 38, 2008. [bib] [pdf]
[2007] Quantum algorithms for the triangle problem (F. Magniez, M. Santha, M. Szegedy), In SIAM Journal on Computing, volume 37, 2007. [bib] [pdf]
[2007] Property testing of regular tree languages (F. Magniez, M. de Rougemont), In Algorithmica, volume 49, 2007. [bib] [pdf]
[2007] Quantum complexity of testing group commutativity (F. Magniez, A. Nayak), In Algorithmica, volume 48, 2007. [bib] [pdf]
[2007] Probabilistic abstraction for model checking: An approach based on property testing (S. Laplante, R. Lassaigne, F. Magniez, S. Peyronnet, M. de Rougemont), In ACM Transactions on Computational Logic, volume 8, 2007. [bib] [pdf]
[2007] Self-testing of universal and fault-tolerant sets of quantum gates (W. van Dam, F. Magniez, M. Mosca, M. Santha), In SIAM Journal on Computing, volume 37, 2007. [bib] [pdf]
[2005] Multi-linearity self-testing with relative error (F. Magniez), In Theory of Computing Systems (TOCS), volume 38, 2005. [bib] [pdf]
[2005] Quantum algorithms for element distinctness (H. Buhrman, C. Dürr, M. Heiligman, P. Høyer, F. Magniez, M. Santha, R. de Wolf), In SIAM Journal on Computing, volume 34, 2005. [bib] [pdf]
[2003] Approximate testing with error relative to input size (M. Kiwi, F. Magniez, M. Santha), In Journal of Computer and System Sciences, volume 66, 2003. [bib] [pdf]
[2003] Efficient quantum algorithms for some instances of the non-Abelian hidden subgroup problem (G. Ivanyos, F. Magniez, M. Santha), In International Journal of Foundations of Computer Science, volume 14, 2003. [bib] [pdf]
Refereed Conference Papers
[2017] Extended Learning Graphs for Triangle Finding (T. Carette, M. Laurière, F. Magniez), In Proceedings of 34th International Symposium on Theoretical Aspects of Computer Science, 2017. [bib] [pdf]
[2017] Streaming Communication Protocols (L. Boczkowski, I. Kerenidis, F. Magniez), In Proceedings of 44th International Colloquium on Automata, Languages, and Programming, 2017. (To appear) [bib] [pdf]
[2016] Stable Matching with Evolving Preferences (V. Kanade, N. Leonardos, F. Magniez), In Proceedings of 20th International Workshop on Randomization and Computation, 2016. [bib] [pdf]
[2016] Streaming Property Testing of Visibly Pushdown Languages (N. François, F. Magniez, M. de Rougemont, O. Serre), In Proceedings of 24rd European Symposium on Algorithms, 2016. [bib] [pdf]
[2014] Optimal parallel quantum query algorithms (S. Jeffery, F. Magniez, R. de Wolf), In Proceedings of 22nd European Symposium on Algorithms, 2014. [bib] [pdf]
[2014] Unidirectional Input/Output Streaming Complexity of Reversal and Sorting (N. François, R. Jain, F. Magniez), In Proceedings of 18th International Workshop on Randomization and Computation, 2014. [bib] [pdf]
[2013] Improved quantum query algorithms for triangle finding and associativity testing (T. Lee, F. Magniez, M. Santha), In Proceedings of 24th ACM-SIAM Symposium on Discrete Algorithms, 2013. (Also presented at QIP'13 as a contributed talk) [bib] [pdf]
[2013] Nested quantum walks with quantum data structures (S. Jeffery, R. Kothari, F. Magniez), In Proceedings of 24th ACM-SIAM Symposium on Discrete Algorithms, 2013. (Also presented at QIP'14 as a contributed talk) [bib] [pdf]
[2013] Streaming complexity of checking priority queues (N. François, F. Magniez), In Proceedings of 30th Symposium on Theoretical Aspects of Computer Science, 2013. [bib] [pdf]
[2013] Time-Efficient Quantum Walks for 3-Distinctness (A. Belovs, A. Childs, S. Jeffery, R. Kothari, F. Magniez), In Proceedings of 40th International Colloquium on Automata, Languages and Programming, 2013. (Also presented at QIP'14 as a contributed talk) [bib] [pdf]
[2012] Maximum matching in semi-streaming with few passes (C. Konrad, F. Magniez, C. Mathieu), In Proceedings of 15th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, 2012. [bib] [pdf] [full version]
[2012] Validating XML documents in the streaming model with external memory (C. Konrad, F. Magniez), In Proceedings of 15th International Conference on Database Theory, 2012. (Best Newcomer Paper) [bib] [pdf]
[2012] Improving quantum query complexity of boolean matrix multiplication using graph collision (S. Jeffery, R. Kothari, F. Magniez), In Proceedings of 39th International Colloquium on Automata, Languages and Programming, 2012. [bib] [pdf]
[2011] The complexity of approximate Nash equilibrium in congestion games with negative delays (F. Magniez, M. de Rougemont, M. Santha, X. Zeitoun), In Proceedings of 7th Workshop on Internet & Network Economics, 2011. [bib] [pdf]
[2011] Improved bounds for the randomized decision tree complexity of recursive majority (F. Magniez, A. Nayak, M. Santha, D. Xiao), In Proceedings of 38th International Colloquium on Automata, Languages and Programming, LNCS, 2011. [bib] [pdf]
[2010] Recognizing well-parenthesized expressions in the streaming model (F. Magniez, C. Mathieu, A. Nayak), In Proceedings of 42nd ACM Symposium on Theory of Computing, 2010. [bib] [pdf]
[2010] Finding is as easy as detecting for quantum walks (H. Krovi, F. Magniez, M. Ozols, J. Roland), In Proceedings of 37th International Colloquium on Automata, Languages and Programming, 2010. (Also presented at QIP'11 as a featured talk) [bib] [pdf]
[2009] On the hitting times of quantum versus random walks (F. Magniez, A. Nayak, P. Richter, M. Santha), In Proceedings of 20th ACM-SIAM Symposium on Discrete Algorithms, 2009. [bib] [pdf]
[2007] Search via quantum walk (F. Magniez, A. Nayak, J. Roland, M. Santha), In Proceedings of 39th ACM Symposium on Theory of Computing, 2007. (Also presented at QIP'07 as a contributed talk) [bib] [pdf]
[2006] Self-testing of quantum circuits (F. Magniez, D. Mayers, M. Mosca, H. Ollivier), In Proceedings of 33rd International Colloquium on Automata, Languages and Programming, LNCS 4051, 2006. (Also presented at QIP'06 as a contributed talk) [bib] [pdf]
[2006] Approximate satisfiability and equivalence (E. Fischer, F. Magniez, M. de Rougemont), In Proceedings of 21st IEEE Symposium on Logic in Computer Science, 2006. [bib] [pdf]
[2005] Quantum algorithms for the triangle problem (F. Magniez, M. Santha, M. Szegedy), In Proceedings of 16th ACM-SIAM Symposium on Discrete Algorithms, 2005. (Also presented at QIP'04 as an invited talk) [bib] [pdf]
[2005] Quantum complexity of testing group commutativity (F. Magniez, A. Nayak), In Proceedings of 32nd International Colloquium on Automata, Languages and Programming, LNCS 3580, 2005. [bib] [pdf]
[2004] Property testing of regular tree languages (F. Magniez, M. de Rougemont), In Proceedings of 31st International Colloquium on Automata, Languages and Programming, LNCS 3142, 2004. [bib] [pdf]
[2004] Lower bounds for randomized and quantum query complexity using Kolmogorov arguments (S. Laplante, F. Magniez), In Proceedings of 19th IEEE Conference on Computational Complexity, 2004. [bib] [pdf]
[2003] Quantum testers for hidden group properties (K. Friedl, F. Magniez, M. Santha, P. Sen), In Proceedings of the 28th International Symposium on Mathematical Foundations of Computer Science, LNCS 2747, 2003. [bib] [pdf]
[2003] Hidden translation and orbit coset in quantum computing (K. Friedl, G. Ivanyos, F. Magniez, M. Santha, P. Sen), In Proceedings of 35th ACM Symposium on Theory of Computing, 2003. (Also presented at QIP'03 as an invited talk) [bib] [pdf]
[2002] Probabilistic abstraction for model checking: An approach based on property testing (S. Laplante, R. Lassaigne, F. Magniez, S. Peyronnet, M. de Rougemont), In Proceedings of 17th IEEE Symposium on Logic in Computer Science, 2002. [bib] [pdf]
[2001] Efficient quantum algorithms for some instances of the non-Abelian hidden subgroup problem (G. Ivanyos, F. Magniez, M. Santha), In Proceedings of 13th ACM Symposium on Parallelism in Algorithms and Architectures, 2001. [bib] [pdf]
[2001] Quantum algorithms for element distinctness (H. Buhrman, C. Dürr, M. Heiligman, P. Høyer, F. Magniez, M. Santha, R. de Wolf), In Proceedings of 15th IEEE Conference on Computational Complexity, 2001. [bib] [pdf]
[2000] Multi-linearity self-testing with relative error (F. Magniez), In Proceedings of 17th Symposium on Theoretical Aspects of Computer Science, LNCS 1770, 2000. [bib] [pdf]
[2000] Self-testing of universal and fault-tolerant sets of quantum gates (W. van Dam, F. Magniez, M. Mosca, M. Santha), In Proceedings of 32nd ACM Symposium on Theory of Computing, 2000. [bib] [pdf]
[1999] Approximate testing with relative error (M. Kiwi, F. Magniez, M. Santha), In Proceedings of 31st ACM Symposium on Theory of Computing, 1999. [bib] [pdf]
Other Publications
[2017] Improved bounds for testing Dyck languages (E. Fischer, F. Magniez, T. Starikovskaya), Technical report, arXiv.org, 2017. [bib] [url] [pdf]
[2015] La physique quantique réinvente les algorithmes (I. Kerenidis, F. Magniez), Chapter in La Recherche, volume 501, 2015. [bib]
[2014] Complexité de communication (I. Kerenidis, F. Magniez, D. Xiao), Chapter in Informatique Mathématique - Une photographie en 2014, Presses Universitaires de Perpignan, 2014. [bib] [pdf]
[2013] Some approximations in Model Checking and Testing (M.C. Gaudel, R. Lassaigne, M. de Rougemont, F. Magniez), Technical report, arXiv.org, 2013. (Survey) [bib] [url] [pdf]
[2009] Special issue in Quantum Computation, Algorithmica 55(3) (F. Magniez, A. Nayak (editors)), Springer, 2009. [bib]
[2007] Vérification approchée - Calcul quantique (F. Magniez), Habilitation, Université Paris-Sud, France, 2007. (Record number 1018) [bib] [pdf]
[2006] Comment calculer quantique (J. Kempe, S. Laplante, F. Magniez), Chapter in La Recherche, volume 398, 2006. [bib] [pdf]
[2000] Auto-test pour les calculs approché et quantique (F. Magniez), PhD thesis, Université Paris-Sud, France, 2000. (Record number 6076) [bib] [pdf]
[2000] Exact and approximate testing/correcting of algebraic functions: A survey (M. Kiwi, F. Magniez, M. Santha), Chapter in Proceedings of 1st Summer School on Theoretical Aspects of Computer Science, LNCS 2292, 2000. (Also ECCC Report TR01-014) [bib] [url] [pdf]
Powered by bibtexbrowser