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

ENCODING has been replaced by BIBTEX_INPUT_ENCODING and OUTPUT_ENCODING
Refereed Articles
2013
[38]Stochastic Cellular Automata: Correlations, Decidability and Simulations (, and ), In Fundamenta Informaticae, volume 126, . [bibtex]
[37]Lower bounds for quantum oblivious transfer (, and ), In Journal of Quantum Information and Computation, volume 13, . [bibtex]
[36]Hidden symmetry subgroup problem (, , and ), In SIAM Journal on Computing, volume 42, . [bibtex]
[35]QMA variants with polynomially many provers (, and ), In Journal of Quantum Information and Computation, volume 13, . [bibtex]
[34]The min mean-weight cycle in a random network ( and ), In Combinatorics, Probability & Computing, volume 22, . [bibtex]
[33]Validating XML documents in the streaming model with external memory ( and ), In ACM Transactions on Database Systems, volume 38, . [bibtex]
2014
[32]Quantum commitments from complexity assumptions (, and ), In Computational Complexity, . [bibtex]
[31]Strong connections between quantum encodings, nonlocality, and cryptography (, and ), In Physical Review A, volume 89, . [bibtex]
[30]Testing graph isotopy on surfaces (), In Discrete & Computational Geometry, volume 51, . [bibtex]
[29]Polynomial time quantum algorithms for certain bivariate hidden polynomial problems (, , and ), In Quantum Information and Computation, volume 14, . [bibtex]
[28]Lower bounds on information complexity via zero-communication protocols and applications (, , , and ), In SIAM Journal on Computing, . [bibtex]
[27]Exponential time complexity of the permanent and the Tutte polynomial (, , , and ), In Transactions on Algorithms, volume 10, . [bibtex]
[26]Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses (), In Journal of ACM, volume 61, . [bibtex]
[25]Hidden translation and orbit coset in quantum computing (, , , and ), In SIAM Journal on Computing, volume 43, . [bibtex]
[24]Privacy in quantum communication complexity (, , and ), In arXiv preprint arXiv:1409.8488, . [bibtex]
[23]Recognizing well-parenthesized expressions in the streaming model (, and ), In SIAM Journal on Computing, volume 43, . [bibtex]
[22]Experimental plug and play quantum coin flipping (, , , , , , and ), In Nature communications, Nature Publishing Group, volume 5, . [bibtex]
2015
[21]A nonmonotone analysis with the primal-dual approach: Online routing of virtual circuits with unknown durations ( and ), In Theor. Comput. Sci., volume 584, . [bibtex]
[20]A Local Algorithm for Generating Preferential Attachment Graphs (, , and ), In Unpublished manuscript, . [bibtex]
[19]Generalized Wong sequences and their applications to Edmonds' problems (, , and ), In Journal of Computer and System Sciences, volume 81, . [bibtex]
[18]Constructing near spanning trees with few local inspections (, , , and ), In Random Struct. Algorithms, volume 50, . [bibtex]
[17]Nonlocality and conflicting interest games (, , , , , and ), In Physical Review Letters, volume 112, . [bibtex]
[16]A simpler proof of existence of quantum weak coin flipping with arbitrarily small bias (, , , and ), In SIAM Journal of Computing (to appear), arXiv preprint arXiv:1402.7166, . [bibtex]
[15]Discrete systolic inequalities and decompositions of triangulated surfaces (, and ), In Discrete & Computational Geometry, volume 53, . [bibtex]
[14]Improved bounds for the randomized decision tree complexity of recursive majority (, , , , and ), In Random Structures & Algorithms, . [bibtex]
2016
[13]Space-Constrained Interval Selection ( and ), In ACM Transactions on Algorithms, . [bibtex]
[12]Shrinking Maxima, Decreasing Costs: New Online Packing and Covering Problems. (, , , and ), In Algorithmica, volume 74, . [bibtex]
[11]Improving Quantum Query Complexity of Boolean Matrix Multiplication Using Graph Collision. (, , and ), In Algorithmica, volume 76, . [bibtex]
[10]Quantum Walks Can Find a Marked Element on Any Graph. (, , and ), In Algorithmica, volume 74, . [bibtex]
[9]Clique Here: On the Distributed Complexity in Fully-Connected Networks. (, , and ), In Parallel Processing Letters, volume 26, . [bibtex]
[8]Information cost of quantum communication protocols. (, , and ), In Quantum Information & Computation, volume 16, . [bibtex]
[7]Approximating Semi-matchings in Streaming and in Two-Party Communication. ( and ), In ACM Trans. Algorithms, volume 12, . [bibtex]
[6]Approximate consistency for transformations on words and trees. ( and ), In Theor. Comput. Sci., volume 626, . [bibtex]
[5]Relative Discrepancy Does Not Separate Information and Communication Complexity (, , , , and ), In ACM Tans. on Computation Theory, volume 9, . [bibtex]
[4]Optimal Parallel Quantum Query Algorithms (, and ), In Algorithmica, Springer Nature, . [bibtex]
[3]Semi-Streaming Set Cover ( and ), In ACM Trans. Algorithms, Association for Computing Machinery (ACM), volume 13, . [bibtex]
2017
[2]Improved Quantum Query Algorithms for Triangle Detection and Associativity Testing. (, and ), In Algorithmica, volume 77, . [bibtex]
[1]Solving systems of diagonal polynomial equations over finite fields. ( and ), In Theor. Comput. Sci., volume 657, . [bibtex]
Refereed Conference Papers
2013
[67]Reordering Buffer Management with Advice (, and ), In Proceedings of 11th Workshop on Approximation and Online Algorithms, . [bibtex]
[66]Shrinking Maxima, Decreasing Costs: New Online Packing and Covering Problems (, , , and ), In Proceedings of 16th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, . [bibtex]
[65]New lower bounds for privacy in communication protocols (, and ), In Proceedings of 7th International Conference on Information Theoretic Security, . [bibtex]
[64]Approximating Semi-matchings in Streaming and in Two-Party Communication ( and ), In Proceedings of 40th International Colloquium on Automata, Languages and Programming, . [bibtex]
[63]Query complexity of matroids ( and ), In Proceedings of 40th International Colloquium on Automata, Languages and Programming, . [bibtex]
[62]Sublinear-time algorithms for monomer-dimer systems on bounded degree graphs ( and ), In Proceedings of 24th International Symposium on Algorithms and Computation, . [bibtex]
[61]Languages with Efficient Zero-Knowledge PCPs are in SZK ( and ), In Proceedings of 10th Theory of Cryptography Conference, . [bibtex]
[60]Approximation of Large Probabilistic Networks by Structured Population Protocols ( and ), In Algebraic Informatics - 5th International Conference, CAI, . [bibtex]
[59]Is privacy compatible with truthfulness? (), In Proceedings of 4th Innovations in Theoretical Computer Science, . [bibtex]
[58]Time-Efficient Quantum Walks for 3-Distinctness (, , , and ), In Proceedings of 40th International Colloquium on Automata, Languages and Programming, . [bibtex]
[57]Streaming complexity of checking priority queues ( and ), In Proceedings of 30th Symposium on Theoretical Aspects of Computer Science, . [bibtex]
[56]Nested quantum walks with quantum data structures (, and ), In Proceedings of 24th ACM-SIAM Symposium on Discrete Algorithms, . [bibtex]
[55]Improved quantum query algorithms for triangle finding and associativity testing (, and ), In Proceedings of 24th ACM-SIAM Symposium on Discrete Algorithms, . [bibtex]
2014
[54]On the complexity of immersed normal surfaces ( and ), In Proceedings of the 30th European Workshop on Computational Geometry, . [bibtex]
[53]Discrete systolic inequalities and decompositions of triangulated surfaces ( and ), In Proceedings of 30th Annual Symposium on Computational Geometry, . [bibtex]
[52]Optimal bounds for parity-oblivious random access codes with applications (, , and ), In Proceedings of 9th Conference on the Theory of Quantum Computation, Communication and Cryptography, . [bibtex]
[51]An efficient quantum algorithm for finding hidden parabolic subgroups in the general linear group (, , , and ), In Proceedings of 39th International Symposium on Mathematical Foundations of Computer Science, . [bibtex]
[50]Approximating $k$-center in planar graphs (, and ), In Proceedings of the 25th Symposium on Discrete Algorithms, . [bibtex]
[49]Facility Location in Evolving Metrics (, and ), In Proceedings of 41st International Colloquium on Automata, Languages and Programming, . [bibtex]
[48]Semi-Streaming Set Cover ( and ), In Proceedings of 41st International Colloquium on Automata, Languages and Programming, . [bibtex]
[47]Sample Complexity Bounds on Differentially Private Learning via Communication Complexity ( and ), In Proceedings of 27th Annual Conference on Learning Theory, . [bibtex]
[46]Generalized Wong sequences and their applications to Edmonds' problems (, , and ), In Proceedings of 31st Symposium on Theoretical Aspects of Computer Science, . [bibtex]
[45]On the complexity of trial and error for constraint satisfaction problems (, , , and ), In Proceedings of 41st International Colloquium on Automata, Languages and Programming, . [bibtex]
[44]First come first served for online slot allocation and huffman coding (, and ), In Proceedings of the 25th Symposium on Discrete Algorithms, . [bibtex]
[43]Redrawing the boundaries on purchasing data from privacy-sensitive individuals (, and ), In Proceedings of 5th Innovations in Theoretical Computer Science, . [bibtex]
[42]AND-compression of NP-complete problems: Streamlined proof and minor observations (), In Proceedings of 9th International Symposium on Parameterized and Exact Computation, . [bibtex]
[41]Unidirectional Input/Output Streaming Complexity of Reversal and Sorting (, and ), In Proceedings of 18th International Workshop on Randomization and Computation, . [bibtex]
[40]Optimal parallel quantum query algorithms ( and ), In Proceedings of 22nd European Symposium on Algorithms, . [bibtex]
[39]StatsReduce in the cloud for approximate Analytics (), In IEEE International Conference on Data Science and Advanced Analytics, DSAA 2014, Shanghai, China, . [bibtex]
2015
[38]Efficient universal computation by molecular co-transcriptional folding (Short announcement) (, , and ), In DNA21, . [bibtex]
[37]Homophily and the Glass Ceiling Effect in Social Networks (, , , , and ), In Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, ITCS 2015, Rehovot, Israel, January 11-13, 2015, . [bibtex]
[36]Effectiveness of Local Search for Geometric Optimization ( and ), In 31st International Symposium on Computational Geometry, SoCG 2015, June 22-25, 2015, Eindhoven, The Netherlands, . [bibtex]
[35]Distributed Maximum Matching in Bounded Degree Graphs (, and ), In Proceedings of the 2015 International Conference on Distributed Computing and Networking, ICDCN 2015, Goa, India, January 4-7, 2015, . [bibtex]
[34]Better Deterministic Online Packet Routing on Grids ( and ), In Proceedings of the 27th ACM on Symposium on Parallelism in Algorithms and Architectures, SPAA 2015, Portland, OR, USA, June 13-15, 2015, . [bibtex]
[33]Brief Announcement: Local Computation Algorithms for Graphs of Non-Constant Degrees (, and ), In Proceedings of the 27th ACM on Symposium on Parallelism in Algorithms and Architectures, SPAA 2015, Portland, OR, USA, June 13-15, 2015, . [bibtex]
[32]On solving systems of diagonal polynomial equations over finite fields ( and ), In Proceedings of 9th International Frontiers of Algorithmics Workshop, . [bibtex]
[31]Separating decision tree complexity from subcube partition complexity (, and ), In Proceedings of 19th International Workshop on Randomization and Computation, . [bibtex]
[30]Near-Linear Query Complexity for Graph Inference (, and ), In Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I, . [bibtex]
[29]Correlation Clustering and Two-edge-connected Augmentation for Planar Graphs (, and ), In 32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015, March 4-7, 2015, Garching, Germany, . [bibtex]
[28]Multicuts in planar and bounded-genus graphs with bounded number of terminals (), In Proceedings of the 23rd European Symposium on Algorithms (ESA), . [bibtex]
[27]A fixed parameter tractable approximation scheme for the optimal cut graph of a surface ( and ), In Proceedings of the 23rd European Symposium on Algorithms (ESA), . [bibtex]
[26]Relative discrepancy does not separate information and communication complexity (, , , , and ), In International Colloquium on Automata, Languages, and Programming, . [bibtex]
[25]Communication complexity of conditional disclosure of secrets and attribute-based encryption (, and ), In Advances in Cryptology–CRYPTO 2015, . [bibtex]
[24]New Constructions for Quantum Money ( and ), In LIPIcs-Leibniz International Proceedings in Informatics, volume 44, . [bibtex]
[23]QMA with subset state witnesses (, and ), In Mathematical Foundations of Computer Science 2015, . [bibtex]
[22]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, . [bibtex]
[21]The value of analytical queries on Social Networks ( and ), In 2015 IEEE International Big Data Conference, MBD-SONET, . [bibtex]
2016
[20]Distance in the Forest Fire Model How far are you from Eve? (, , , and ), In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, . [bibtex]
[19]Approximating connectivity domination in weighted bounded-genus graphs (, , , and ), In Proceedings of the 48th Annual ACM Symposium on Theory of Computing (STOC), . [bibtex]
[18]Stable Matching with Evolving Preferences. (, and ), In , . [bibtex]
[17]A Constant Approximation Algorithm for Scheduling Packets on Line Networks. (, and ), In , . [bibtex]
[16]Streaming Property Testing of Visibly Pushdown Languages. (, , and ), In , . [bibtex]
[15]Online Budgeted Maximum Coverage. ( and ), In , . [bibtex]
[14]Unconditionally Secure Computation with Reduced Interaction. (, , and ), In , . [bibtex]
[13]Separations in Communication Complexity Using Cheat Sheets and Information Complexity. (, , , , , , and ), In , . [bibtex]
[12]Linear Time Algorithm for Quantum 2SAT. (, , and ), In , . [bibtex]
[11]On the Complexity of Probabilistic Trials for Hidden Satisfiability Problems. (, , , , and ), In , . [bibtex]
[10]Multi-Party Protocols, Information Complexity and Privacy. (, and ), In , . [bibtex]
[9]Separations in query complexity based on pointer functions. (, , , , and ), In , . [bibtex]
[8]Robust Bell Inequalities from Communication Complexity. (, , , and ), In , . [bibtex]
[7]Non-local Probes Do Not Help with Many Graph Problems. (, , , and ), In , . [bibtex]
2017
[6]On the Polynomial Parity Argument complexity of the Combinatorial Nullstellensatz (, , , and ), In , . [bibtex]
[5]Streaming Communication Protocols (, and ), In , . [bibtex]
[4]Sublinear Random Access Generators for Preferential Attachment Graphs (, , and ), In , . [bibtex]
[3]Quantum recommendation systems ( and ), In , . [bibtex]
[2]Extended Learning Graphs for Triangle Finding. (, and ), In , . [bibtex]
[1]Provably secure key establishment against quantum adversaries (, , , , and ), In , . [bibtex]
Other Publications
2014
[6]De la carte au territoire ? ( and ), Chapter in Images des mathématiques, CNRS, . [bibtex]
2015
[5]Quantum and randomized query complexities (), Chapter in Proceedings of 12th International Conference on Theory and Applications of Models of Computation, . [bibtex]
[4]La médiation en informatique vue par le CNRS ( and ), Chapter in 1024 – Bulletin de la société informatique de France, Société Informatique de France, . [bibtex]
[3]Les hottes du Père Noël (), Chapter in 1024 – Bulletin de la société informatique de France, Société Informatique de France, . [bibtex]
[2]La physique quantique réinvente les algorithmes ( and ), Chapter in La Recherche, volume 501, . [bibtex]
2016
[1]Computational topology of graphs on surfaces (), Chapter in Handbook of Discrete and Computational Geometry (Goodman, Jacob E., O'Rourke, Joseph, eds.), CRC Press LLC, . [bibtex]