### Recent

Refereed Articles

[2017] | Improved quantum query algorithms for triangle finding and associativity testing , In Algorithmica, volume 77, 2017. [bib] [pdf] |

[2017] | Optimal parallel quantum query algorithms , In Algorithmica, volume 79, 2017. (To appear) [bib] [pdf] |

[2016] | Improved bounds for the randomized decision tree complexity of recursive majority , In Random Structures & Algorithms, volume 48, 2016. [bib] [pdf] |

[2016] | Quantum walks can find a marked element on any graph , In Algorithmica, volume 74, 2016. [bib] [pdf] |

[2016] | Improving Quantum Query Complexity of Boolean Matrix Multiplication Using Graph Collision , In Algorithmica, volume 76, 2016. [bib] [pdf] |

Refereed Conference Papers

[2017] | Extended Learning Graphs for Triangle Finding , In Proceedings of 34th International Symposium on Theoretical Aspects of Computer Science, 2017. [bib] [pdf] |

[2017] | Streaming Communication Protocols , In Proceedings of 44th International Colloquium on Automata, Languages, and Programming, 2017. [bib] [pdf] |

[2016] | Stable Matching with Evolving Preferences , In Proceedings of 20th International Workshop on Randomization and Computation, 2016. [bib] [pdf] |

[2016] | Streaming Property Testing of Visibly Pushdown Languages , In Proceedings of 24rd European Symposium on Algorithms, 2016. [bib] [pdf] |

Other Publications

[2017] | Improved bounds for testing Dyck languages , 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 , In Algorithmica, volume 77, 2017. [bib] [pdf] |

[2017] | Optimal parallel quantum query algorithms , In Algorithmica, volume 79, 2017. (To appear) [bib] [pdf] |

[2016] | Improved bounds for the randomized decision tree complexity of recursive majority , In Random Structures & Algorithms, volume 48, 2016. [bib] [pdf] |

[2016] | Quantum walks can find a marked element on any graph , In Algorithmica, volume 74, 2016. [bib] [pdf] |

[2016] | Improving Quantum Query Complexity of Boolean Matrix Multiplication Using Graph Collision , In Algorithmica, volume 76, 2016. [bib] [pdf] |

[2014] | Recognizing well-parenthesized expressions in the streaming model , In SIAM Journal on Computing, volume 43, 2014. [bib] [pdf] |

[2014] | Hidden translation and orbit coset in quantum computing , In SIAM Journal on Computing, volume 43, 2014. [bib] [pdf] |

[2013] | Validating XML documents in the streaming model with external memory , 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 , In Algorithmica, volume 63, 2012. [bib] [pdf] |

[2012] | A learning graph based quantum query algorithm for finding constant-size subgraphs , In Chicago Journal of Theoretical Computer Science, 2012. [bib] [pdf] |

[2011] | Search via quantum walk , In SIAM Journal on Computing, volume 40, 2011. [bib] [pdf] |

[2010] | Strong no-go theorem for gaussian quantum bit commitment , In Physical Review A, volume 81, 2010. [bib] [pdf] |

[2010] | Approximate satisfiability and equivalence , In SIAM Journal on Computing, volume 39, 2010. [bib] [pdf] |

[2009] | Quantum testers for hidden group properties , 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 , In SIAM Journal on Computing, volume 38, 2008. [bib] [pdf] |

[2007] | Quantum algorithms for the triangle problem , In SIAM Journal on Computing, volume 37, 2007. [bib] [pdf] |

[2007] | Property testing of regular tree languages , In Algorithmica, volume 49, 2007. [bib] [pdf] |

[2007] | Quantum complexity of testing group commutativity , In Algorithmica, volume 48, 2007. [bib] [pdf] |

[2007] | Probabilistic abstraction for model checking: An approach based on property testing , In ACM Transactions on Computational Logic, volume 8, 2007. [bib] [pdf] |

[2007] | Self-testing of universal and fault-tolerant sets of quantum gates , In SIAM Journal on Computing, volume 37, 2007. [bib] [pdf] |

[2005] | Multi-linearity self-testing with relative error , In Theory of Computing Systems (TOCS), volume 38, 2005. [bib] [pdf] |

[2005] | Quantum algorithms for element distinctness , In SIAM Journal on Computing, volume 34, 2005. [bib] [pdf] |

[2003] | Approximate testing with error relative to input size , 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 , In International Journal of Foundations of Computer Science, volume 14, 2003. [bib] [pdf] |

Refereed Conference Papers

[2017] | Extended Learning Graphs for Triangle Finding , In Proceedings of 34th International Symposium on Theoretical Aspects of Computer Science, 2017. [bib] [pdf] |

[2017] | Streaming Communication Protocols , In Proceedings of 44th International Colloquium on Automata, Languages, and Programming, 2017. [bib] [pdf] |

[2016] | Stable Matching with Evolving Preferences , In Proceedings of 20th International Workshop on Randomization and Computation, 2016. [bib] [pdf] |

[2016] | Streaming Property Testing of Visibly Pushdown Languages , In Proceedings of 24rd European Symposium on Algorithms, 2016. [bib] [pdf] |

[2014] | Optimal parallel quantum query algorithms , In Proceedings of 22nd European Symposium on Algorithms, 2014. [bib] [pdf] |

[2014] | Unidirectional Input/Output Streaming Complexity of Reversal and Sorting , In Proceedings of 18th International Workshop on Randomization and Computation, 2014. [bib] [pdf] |

[2013] | Improved quantum query algorithms for triangle finding and associativity testing , 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 , 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 , In Proceedings of 30th Symposium on Theoretical Aspects of Computer Science, 2013. [bib] [pdf] |

[2013] | Time-Efficient Quantum Walks for 3-Distinctness , 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 , 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 , 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 , 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 , In Proceedings of 7th Workshop on Internet & Network Economics, 2011. [bib] [pdf] |

[2011] | Improved bounds for the randomized decision tree complexity of recursive majority , In Proceedings of 38th International Colloquium on Automata, Languages and Programming, LNCS, 2011. [bib] [pdf] |

[2010] | Recognizing well-parenthesized expressions in the streaming model , In Proceedings of 42nd ACM Symposium on Theory of Computing, 2010. [bib] [pdf] |

[2010] | Finding is as easy as detecting for quantum walks , 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 , In Proceedings of 20th ACM-SIAM Symposium on Discrete Algorithms, 2009. [bib] [pdf] |

[2007] | Search via quantum walk , 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 , 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 , In Proceedings of 21st IEEE Symposium on Logic in Computer Science, 2006. [bib] [pdf] |

[2005] | Quantum algorithms for the triangle problem , 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 , In Proceedings of 32nd International Colloquium on Automata, Languages and Programming, LNCS 3580, 2005. [bib] [pdf] |

[2004] | Property testing of regular tree languages , 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 , In Proceedings of 19th IEEE Conference on Computational Complexity, 2004. [bib] [pdf] |

[2003] | Quantum testers for hidden group properties , 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 , 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 , 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 , In Proceedings of 13th ACM Symposium on Parallelism in Algorithms and Architectures, 2001. [bib] [pdf] |

[2001] | Quantum algorithms for element distinctness , In Proceedings of 15th IEEE Conference on Computational Complexity, 2001. [bib] [pdf] |

[2000] | Multi-linearity self-testing with relative error , 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 , In Proceedings of 32nd ACM Symposium on Theory of Computing, 2000. [bib] [pdf] |

[1999] | Approximate testing with relative error , In Proceedings of 31st ACM Symposium on Theory of Computing, 1999. [bib] [pdf] |

Other Publications

[2017] | Improved bounds for testing Dyck languages , Technical report, arXiv.org, 2017. [bib] [url] [pdf] |

[2015] | La physique quantique réinvente les algorithmes , Chapter in La Recherche, volume 501, 2015. [bib] |

[2014] | Complexité de communication , Chapter in Informatique Mathématique - Une photographie en 2014, Presses Universitaires de Perpignan, 2014. [bib] [pdf] |

[2013] | Some approximations in Model Checking and Testing , Technical report, arXiv.org, 2013. (Survey) [bib] [url] [pdf] |

[2009] | Special issue in Quantum Computation, Algorithmica 55(3) , Springer, 2009. [bib] |

[2007] | Vérification approchée - Calcul quantique , Habilitation, Université Paris-Sud, France, 2007. (Record number 1018) [bib] [pdf] |

[2006] | Comment calculer quantique , Chapter in La Recherche, volume 398, 2006. [bib] [pdf] |

[2000] | Auto-test pour les calculs approché et quantique , PhD thesis, Université Paris-Sud, France, 2000. (Record number 6076) [bib] [pdf] |

[2000] | Exact and approximate testing/correcting of algebraic functions: A survey , 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