# ANR support

All related publications need to mention the support from the project as follows:
** Supported by the French ANR Blanc project ANR-12-BS02-005 (RDAM)**

# List of publications

Refereed Articles

[1] | Solving systems of diagonal polynomial equations over finite fields. , In Theor. Comput. Sci., volume 657, 2017. [bib] |

[2] | Improved Quantum Query Algorithms for Triangle Detection and Associativity Testing. , In Algorithmica, volume 77, 2017. [bib] |

[3] | Relative Discrepancy Does Not Separate Information and Communication Complexity , In ACM Tans. on Computation Theory, volume 9, 2016. [bib] |

[4] | Approximate consistency for transformations on words and trees. , In Theor. Comput. Sci., volume 626, 2016. [bib] |

[5] | Approximating Semi-matchings in Streaming and in Two-Party Communication. , In ACM Trans. Algorithms, volume 12, 2016. [bib] |

[6] | Information cost of quantum communication protocols. , In Quantum Information & Computation, volume 16, 2016. [bib] |

[7] | Clique Here: On the Distributed Complexity in Fully-Connected Networks. , In Parallel Processing Letters, volume 26, 2016. [bib] |

[8] | Quantum Walks Can Find a Marked Element on Any Graph. , In Algorithmica, volume 74, 2016. [bib] |

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

[10] | Shrinking Maxima, Decreasing Costs: New Online Packing and Covering Problems. , In Algorithmica, volume 74, 2016. [bib] |

[11] | Space-Constrained Interval Selection , In ACM Transactions on Algorithms, 2016. (Accepted for publication) [bib] |

[12] | Optimal Parallel Quantum Query Algorithms , In Algorithmica, Springer Nature, 2016. [bib] |

[13] | Semi-Streaming Set Cover , In ACM Trans. Algorithms, Association for Computing Machinery (ACM), volume 13, 2016. [bib] |

[14] | Improved bounds for the randomized decision tree complexity of recursive majority , In Random Structures & Algorithms, 2015. (To appear) [bib] |

[15] | Discrete systolic inequalities and decompositions of triangulated surfaces , In Discrete & Computational Geometry, volume 53, 2015. [bib] |

[16] | A simpler proof of existence of quantum weak coin flipping with arbitrarily small bias , In SIAM Journal of Computing (to appear), arXiv preprint arXiv:1402.7166, 2015. [bib] |

[17] | Nonlocality and conflicting interest games , In Physical Review Letters, volume 112, 2015. [bib] |

[18] | Constructing near spanning trees with few local inspections , In Random Struct. Algorithms, volume 50, 2015. [bib] |

[19] | Generalized Wong sequences and their applications to Edmonds' problems , In Journal of Computer and System Sciences, volume 81, 2015. [bib] |

[20] | A Local Algorithm for Generating Preferential Attachment Graphs , In Unpublished manuscript, 2015. [bib] |

[21] | A nonmonotone analysis with the primal-dual approach: Online routing of virtual circuits with unknown durations , In Theor. Comput. Sci., volume 584, 2015. [bib] |

[22] | Experimental plug and play quantum coin flipping , In Nature communications, Nature Publishing Group, volume 5, 2014. [bib] |

[23] | Recognizing well-parenthesized expressions in the streaming model , In SIAM Journal on Computing, volume 43, 2014. (Joint IRIF/DIENS publication) [bib] |

[24] | Privacy in quantum communication complexity , In arXiv preprint arXiv:1409.8488, 2014. [bib] |

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

[26] | Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses , In Journal of ACM, volume 61, 2014. [bib] |

[27] | Exponential time complexity of the permanent and the Tutte polynomial , In Transactions on Algorithms, volume 10, 2014. [bib] |

[28] | Lower bounds on information complexity via zero-communication protocols and applications , In SIAM Journal on Computing, 2014. (Special issue for FOCS 2012. To appear) [bib] |

[29] | Polynomial time quantum algorithms for certain bivariate hidden polynomial problems , In Quantum Information and Computation, volume 14, 2014. [bib] |

[30] | Testing graph isotopy on surfaces , In Discrete & Computational Geometry, volume 51, 2014. [bib] |

[31] | Strong connections between quantum encodings, nonlocality, and cryptography , In Physical Review A, volume 89, 2014. [bib] |

[32] | Quantum commitments from complexity assumptions , In Computational Complexity, 2014. (To appear) [bib] |

[33] | 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] |

[34] | The min mean-weight cycle in a random network , In Combinatorics, Probability & Computing, volume 22, 2013. [bib] |

[35] | QMA variants with polynomially many provers , In Journal of Quantum Information and Computation, volume 13, 2013. [bib] |

[36] | Hidden symmetry subgroup problem , In SIAM Journal on Computing, volume 42, 2013. [bib] |

[37] | Lower bounds for quantum oblivious transfer , In Journal of Quantum Information and Computation, volume 13, 2013. [bib] |

[38] | Stochastic Cellular Automata: Correlations, Decidability and Simulations , In Fundamenta Informaticae, volume 126, 2013. [bib] |

Refereed Conference Papers

[39] | Provably secure key establishment against quantum adversaries , In 12nd Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2017, June 14-16, 2017, Paris, France, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. [bib] |

[40] | Extended Learning Graphs for Triangle Finding. , In 34th Symposium on Theoretical Aspects of Computer Science, STACS 2017, March 8-11, 2017, Hannover, Germany, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, volume 66, 2017. [bib] |

[41] | Quantum recommendation systems , In Proceedings of the 2017 Conference on Innovations in Theoretical Computer Science, ITCS'17, Berkeley, CA, USA, January 9-11, 2017, ACM, 2017. [bib] |

[42] | Sublinear Random Access Generators for Preferential Attachment Graphs , In 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. [bib] |

[43] | Streaming Communication Protocols , In 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. [bib] |

[44] | On the Polynomial Parity Argument complexity of the Combinatorial Nullstellensatz , In 32nd Conference on Computational Complexity, CCC 2017, July 6-9, 2017, Riga, Latvia, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. [bib] |

[45] | Non-local Probes Do Not Help with Many Graph Problems. , In , 2016. [bib] |

[46] | Robust Bell Inequalities from Communication Complexity. , In 11th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2016, September 27-29, 2016, Berlin, Germany, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, volume 61, 2016. [bib] |

[47] | Separations in query complexity based on pointer functions. , In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, ACM, 2016. [bib] |

[48] | Multi-Party Protocols, Information Complexity and Privacy. , In 41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016, August 22-26, 2016 - Kraków, Poland, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, volume 58, 2016. [bib] |

[49] | On the Complexity of Probabilistic Trials for Hidden Satisfiability Problems. , In 41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016, August 22-26, 2016 - Kraków, Poland, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, volume 58, 2016. [bib] |

[50] | Linear Time Algorithm for Quantum 2SAT. , In 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. [bib] |

[51] | Separations in Communication Complexity Using Cheat Sheets and Information Complexity. , In IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, New Brunswick, New Jersey, USA, 9-11 October 2016, IEEE Computer Society, 2016. [bib] |

[52] | Unconditionally Secure Computation with Reduced Interaction. , In Advances in Cryptology - EUROCRYPT 2016 - 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria, May 8-12, 2016, Proceedings, Part II, Springer, volume 9666, 2016. [bib] |

[53] | Online Budgeted Maximum Coverage. , In 24th Annual European Symposium on Algorithms, ESA 2016, August 22-24, 2016, Aarhus, Denmark, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, volume 57, 2016. [bib] |

[54] | Streaming Property Testing of Visibly Pushdown Languages. , In 24th Annual European Symposium on Algorithms, ESA 2016, August 22-24, 2016, Aarhus, Denmark, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, volume 57, 2016. [bib] |

[55] | A Constant Approximation Algorithm for Scheduling Packets on Line Networks. , In 24th Annual European Symposium on Algorithms, ESA 2016, August 22-24, 2016, Aarhus, Denmark, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, volume 57, 2016. [bib] |

[56] | Stable Matching with Evolving Preferences. , In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2016, September 7-9, 2016, Paris, France, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, volume 60, 2016. [bib] |

[57] | Approximating connectivity domination in weighted bounded-genus graphs , In Proceedings of the 48th Annual ACM Symposium on Theory of Computing (STOC), 2016. (To appear) [bib] |

[58] | Distance in the Forest Fire Model How far are you from Eve? , In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, 2016. (Joint IRIF/DIENS publication) [bib] |

[59] | The value of analytical queries on Social Networks , In 2015 IEEE International Big Data Conference, MBD-SONET, 2015. [bib] |

[60] | The First-Order Contiguity of Sparse Random Graphs with Prescribed Degrees , In Theory and Applications of Models of Computation, Volume 9076 of the series Lecture Notes in Computer Science, 2015. [bib] |

[61] | QMA with subset state witnesses , In Mathematical Foundations of Computer Science 2015, 2015. [bib] |

[62] | New Constructions for Quantum Money , In LIPIcs-Leibniz International Proceedings in Informatics, volume 44, 2015. [bib] |

[63] | Communication complexity of conditional disclosure of secrets and attribute-based encryption , In Advances in Cryptology--CRYPTO 2015, 2015. [bib] |

[64] | Relative discrepancy does not separate information and communication complexity , In International Colloquium on Automata, Languages, and Programming, 2015. [bib] |

[65] | A fixed parameter tractable approximation scheme for the optimal cut graph of a surface , In Proceedings of the 23rd European Symposium on Algorithms (ESA), 2015. [bib] |

[66] | Multicuts in planar and bounded-genus graphs with bounded number of terminals , In Proceedings of the 23rd European Symposium on Algorithms (ESA), 2015. [bib] |

[67] | Correlation Clustering and Two-edge-connected Augmentation for Planar Graphs , In 32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015, March 4-7, 2015, Garching, Germany, 2015. [bib] |

[68] | Near-Linear Query Complexity for Graph Inference , In Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I, 2015. [bib] |

[69] | Separating decision tree complexity from subcube partition complexity , In Proceedings of 19th International Workshop on Randomization and Computation, 2015. [bib] |

[70] | On solving systems of diagonal polynomial equations over finite fields , In Proceedings of 9th International Frontiers of Algorithmics Workshop, 2015. [bib] |

[71] | Brief Announcement: Local Computation Algorithms for Graphs of Non-Constant Degrees , In Proceedings of the 27th ACM on Symposium on Parallelism in Algorithms and Architectures, SPAA 2015, Portland, OR, USA, June 13-15, 2015, 2015. [bib] |

[72] | Better Deterministic Online Packet Routing on Grids , In Proceedings of the 27th ACM on Symposium on Parallelism in Algorithms and Architectures, SPAA 2015, Portland, OR, USA, June 13-15, 2015, 2015. [bib] |

[73] | Distributed Maximum Matching in Bounded Degree Graphs , In Proceedings of the 2015 International Conference on Distributed Computing and Networking, ICDCN 2015, Goa, India, January 4-7, 2015, 2015. [bib] |

[74] | Effectiveness of Local Search for Geometric Optimization , In 31st International Symposium on Computational Geometry, SoCG 2015, June 22-25, 2015, Eindhoven, The Netherlands, 2015. [bib] |

[75] | Homophily and the Glass Ceiling Effect in Social Networks , In Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, ITCS 2015, Rehovot, Israel, January 11-13, 2015, 2015. (Joint IRIF/DIENS publication) [bib] |

[76] | Efficient universal computation by molecular co-transcriptional folding (Short announcement) , In DNA21, 2015. [bib] |

[77] | StatsReduce in the cloud for approximate Analytics , In IEEE International Conference on Data Science and Advanced Analytics, DSAA 2014, Shanghai, China, 2014. [bib] |

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

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

[80] | AND-compression of NP-complete problems: Streamlined proof and minor observations , In Proceedings of 9th International Symposium on Parameterized and Exact Computation, 2014. [bib] |

[81] | Redrawing the boundaries on purchasing data from privacy-sensitive individuals , In Proceedings of 5th Innovations in Theoretical Computer Science, 2014. [bib] |

[82] | First come first served for online slot allocation and huffman coding , In Proceedings of the 25th Symposium on Discrete Algorithms, 2014. [bib] |

[83] | On the complexity of trial and error for constraint satisfaction problems , In Proceedings of 41st International Colloquium on Automata, Languages and Programming, 2014. (To appear) [bib] |

[84] | Generalized Wong sequences and their applications to Edmonds' problems , In Proceedings of 31st Symposium on Theoretical Aspects of Computer Science, 2014. [bib] |

[85] | Sample Complexity Bounds on Differentially Private Learning via Communication Complexity , In Proceedings of 27th Annual Conference on Learning Theory, 2014. [bib] |

[86] | Semi-Streaming Set Cover , In Proceedings of 41st International Colloquium on Automata, Languages and Programming, 2014. [bib] |

[87] | Facility Location in Evolving Metrics , In Proceedings of 41st International Colloquium on Automata, Languages and Programming, 2014. (Joint IRIF/DIENS publication) [bib] |

[88] | Approximating $k$-center in planar graphs , In Proceedings of the 25th Symposium on Discrete Algorithms, 2014. [bib] |

[89] | An efficient quantum algorithm for finding hidden parabolic subgroups in the general linear group , In Proceedings of 39th International Symposium on Mathematical Foundations of Computer Science, 2014. [bib] |

[90] | Optimal bounds for parity-oblivious random access codes with applications , In Proceedings of 9th Conference on the Theory of Quantum Computation, Communication and Cryptography, 2014. (To appear) [bib] |

[91] | Discrete systolic inequalities and decompositions of triangulated surfaces , In Proceedings of 30th Annual Symposium on Computational Geometry, 2014. [bib] |

[92] | On the complexity of immersed normal surfaces , In Proceedings of the 30th European Workshop on Computational Geometry, 2014. (To appear) [bib] |

[93] | Improved quantum query algorithms for triangle finding and associativity testing , In Proceedings of 24th ACM-SIAM Symposium on Discrete Algorithms, 2013. [bib] |

[94] | Nested quantum walks with quantum data structures , In Proceedings of 24th ACM-SIAM Symposium on Discrete Algorithms, 2013. [bib] |

[95] | Streaming complexity of checking priority queues , In Proceedings of 30th Symposium on Theoretical Aspects of Computer Science, 2013. [bib] |

[96] | Time-Efficient Quantum Walks for 3-Distinctness , In Proceedings of 40th International Colloquium on Automata, Languages and Programming, 2013. [bib] |

[97] | Is privacy compatible with truthfulness? , In Proceedings of 4th Innovations in Theoretical Computer Science, 2013. [bib] |

[98] | Approximation of Large Probabilistic Networks by Structured Population Protocols , In Algebraic Informatics - 5th International Conference, CAI, 2013. [bib] |

[99] | Languages with Efficient Zero-Knowledge PCPs are in SZK , In Proceedings of 10th Theory of Cryptography Conference, 2013. [bib] |

[100] | Sublinear-time algorithms for monomer-dimer systems on bounded degree graphs , In Proceedings of 24th International Symposium on Algorithms and Computation, 2013. [bib] |

[101] | Query complexity of matroids , In Proceedings of 40th International Colloquium on Automata, Languages and Programming, 2013. [bib] |

[102] | Approximating Semi-matchings in Streaming and in Two-Party Communication , In Proceedings of 40th International Colloquium on Automata, Languages and Programming, 2013. [bib] |

[103] | New lower bounds for privacy in communication protocols , In Proceedings of 7th International Conference on Information Theoretic Security, 2013. [bib] |

[104] | Shrinking Maxima, Decreasing Costs: New Online Packing and Covering Problems , In Proceedings of 16th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, 2013. [bib] |

[105] | Reordering Buffer Management with Advice , In Proceedings of 11th Workshop on Approximation and Online Algorithms, 2013. [bib] |

Other Publications

[106] | Computational topology of graphs on surfaces , Chapter in Handbook of Discrete and Computational Geometry (Jacob E. Goodman, Joseph O'Rourke, eds.), CRC Press LLC, 2016. (To appear) [bib] |

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

[108] | Quantum and randomized query complexities , Chapter in Proceedings of 12th International Conference on Theory and Applications of Models of Computation, 2015. (Invited talk) [bib] |

[109] | Les hottes du Père Noël , Chapter in 1024 -- Bulletin de la société informatique de France, Société Informatique de France, 2015. [bib] |

[110] | La médiation en informatique vue par le CNRS , Chapter in 1024 -- Bulletin de la société informatique de France, Société Informatique de France, 2015. [bib] |

[111] | De la carte au territoire ? , Chapter in Images des mathématiques, CNRS, 2014. [bib] |

Powered by bibtexbrowser