Search results for "Communication complexity"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
3	Pierre Fraigniaud, George Giakkoupis	On the bit communication complexity of randomized rumor spreading.	SPAA	2010	DBLP DOI BibTeX RDF	bit communication complexity, random phone call, rumor spreading
3	Eyal Kushilevitz, Enav Weinreb	On the complexity of communication complexity.	STOC	2009	DBLP DOI BibTeX RDF	protocol tree, lower bounds, communication complexity, hardness of approximation, pseudo random functions
3	Rafail Ostrovsky, William E. Skeith III	Communication Complexity in Algebraic Two-Party Protocols.	CRYPTO	2008	DBLP DOI BibTeX RDF	fully homomorphic encryption, PIR writing, algebraic lower bounds, communication complexity, keyword search, private information retrieval, homomorphic encryption
3	Nati Linial, Adi Shraibman	Learning Complexity vs. Communication Complexity.	IEEE Conference on Computational Complexity	2008	DBLP DOI BibTeX RDF	large margin classifiers, communication complexity, discrepancy, rigidity
3	Dmitry Gavinsky, Pavel Pudlák	Exponential Separation of Quantum and Classical Non-interactive Multi-party Communication Complexity.	IEEE Conference on Computational Complexity	2008	DBLP DOI BibTeX RDF	separation of communication classes, communication complexity, quantum communication
3	Alexander A. Sherstov	Communication Complexity under Product and Nonproduct Distributions.	IEEE Conference on Computational Complexity	2008	DBLP DOI BibTeX RDF	Randomized/distributional communication complexity, product/nonproduct distributions, Yao's Minimax Principle
3	Harry Buhrman, Michal Koucký, Nikolai K. Vereshchagin	Randomised Individual Communication Complexity.	IEEE Conference on Computational Complexity	2008	DBLP DOI BibTeX RDF	individual communication complexity, Kolmogorov complexity, rounds, randomized protocols
3	Rahul Jain, Hartmut Klauck, Ashwin Nayak	Direct product theorems for classical communication complexity via subdistribution bounds: extended abstract.	STOC	2008	DBLP DOI BibTeX RDF	rectangle bounds, subdistribution bounds, information theory, communication complexity, direct product
3	Sergiu Hart, Yishay Mansour	The communication complexity of uncoupled nash equilibrium procedures.	STOC	2007	DBLP DOI BibTeX RDF	communication complexity, computational game theory
3	Nati Linial, Adi Shraibman	Lower bounds in communication complexity based on factorization norms.	STOC	2007	DBLP DOI BibTeX RDF	factorization norms, communication complexity, discrepancy, Fourier analysis
3	Ariel D. Procaccia, Jeffrey S. Rosenschein	The communication complexity of coalition formation among autonomous agents.	AAMAS	2006	DBLP DOI BibTeX RDF	communication complexity, coalition formation
3	Dmitry Gavinsky, Julia Kempe, Oded Regev, Ronald de Wolf	Bounded-error quantum state identification and exponential separations in communication complexity.	STOC	2006	DBLP DOI BibTeX RDF	quantum computing, randomness, communication complexity, entanglement, state identification
3	Vincent Conitzer, Tuomas Sandholm	Communication complexity of common voting rules.	ACM Conference on Electronic Commerce	2005	DBLP DOI BibTeX RDF	communication complexity, voting
3	Ziv Bar-Yossef, T. S. Jayram, Iordanis Kerenidis	Exponential separation of quantum and classical one-way communication complexity.	STOC	2004	DBLP DOI BibTeX RDF	hidden matching, quantum computation, communication complexity, separation
3	Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar, D. Sivakumar	Information Theory Methods in Communication Complexity. (PDF / PS)	IEEE Conference on Computational Complexity	2002	DBLP DOI BibTeX RDF	Fano's inequality, Maximum Likelihood Estimate Principle, Information Theory, Communication complexity
3	Ran Raz	The BNS-Chung criterion for multi-party communication complexity.	Computational Complexity	2000	DBLP DOI BibTeX RDF	Communication complexity, discrepancy
3	Ronald de Wolf	Characterization of Non-Deterministic Quantum Query and Quantum Communication Complexity. (PDF / PS)	IEEE Conference on Computational Complexity	2000	DBLP DOI BibTeX RDF	non-deterministic computation, Quantum computing, communication complexity, query complexity
3	Vince Grolmusz	Harmonic Analysis, Real Approximation, and the Communication Complexity of Boolean Functions.	Algorithmica	1999	DBLP DOI BibTeX RDF	Complexity of Boolean functions, Communication complexity, Fourier coefficients
3	Stephen Ponzio, Jaikumar Radhakrishnan, Srinivasan Venkatesh	The Communication Complexity of Pointer Chasing Applications of Entropy and Sampling (Abstract). (PDF / PS)	IEEE Conference on Computational Complexity	1999	DBLP DOI BibTeX RDF	pointer chasing, entropy, Communication complexity
3	Juraj Hromkovic, Georg Schnitger	Communication Complexity and Sequential Compuation.	MFCS	1997	DBLP DOI BibTeX RDF	Las Vegas, communication complexity, automata, determinism, computational and structural complexity
3	Pavol Duris, Juraj Hromkovic, José D. P. Rolim, Georg Schnitger	Las Vegas Versus Determinism for One-way Communication Complexity, Finite Automata, and Polynomial-time Computations.	STACS	1997	DBLP DOI BibTeX RDF	Las Vegas, communication complexity, automata, determinism, computational and structural complexity
3	Gábor Tardos, Uri Zwick	The Communication Complexity of the Universal Relation. (PDF / PS)	IEEE Conference on Computational Complexity	1997	DBLP DOI BibTeX RDF	protocols, communication complexity
3	Ran Raz, Pierre McKenzie	Separation of the Monotone NC Hierarchy.	FOCS	1997	DBLP DOI BibTeX RDF	monotone NC hierarchy, tight lower bounds, monotone depth, DART games, communication complexity, communication complexity, search problems, monotone Boolean function
3	Satyanarayana V. Lokam	Spectral Methods for Matrix Rigidity with Applications to Size-Depth Tradeoffs and Communication Complexity.	FOCS	1995	DBLP DOI BibTeX RDF	matrix rigidity, size-depth tradeoffs, explicit matrices, lower bounds, communication complexity, communication complexity, matrix algebra, complexity theory, arithmetic circuits
3	Noam Nisan, Avi Wigderson	On Rank vs. Communication Complexity	FOCS	1994	DBLP DOI BibTeX RDF	associated function, associated matrix, deterministic communication complexity, rank, Boolean function, communication complexity, matrix
3	Carsten Damm, Matthias Krause, Christoph Meinel, Stephan Waack	Separating Counting Communication Complexity Classes.	STACS	1992	DBLP DOI BibTeX RDF	complexity of Boolean function, communication complexity and distributed computing, probabilism, lower bound arguments, separation of complexity classes
3	Ran Canetti, Oded Goldreich	Bounds on Tradeoffs between Randomness and Communication Complexity	FOCS	1990	DBLP DOI BibTeX RDF	random bits, deterministic communication complexity, randomness, communication complexity, tradeoffs, quantitative
3	Danny Dolev, Tomás Feder	Multiparty Communication Complexity	FOCS	1989	DBLP DOI BibTeX RDF	nondeterministic communication complexity, information lower bound, Boolean function, communication complexity
2	Eyal Kushilevitz	Communication Complexity: From Two-Party to Multiparty.	SIROCCO	2010	DBLP DOI BibTeX RDF
2	Russell Impagliazzo, Ryan Williams	Communication Complexity with Synchronized Clocks.	IEEE Conference on Computational Complexity	2010	DBLP DOI BibTeX RDF	time-communication tradeoffs, lower bounds, communication complexity
2	Rahul Jain, Hartmut Klauck	The Partition Bound for Classical Communication Complexity and Query Complexity.	IEEE Conference on Computational Complexity	2010	DBLP DOI BibTeX RDF	Partition Bound, Lower Bounds, Linear Programming, Communication Complexity, Query Complexity
2	Hartmut Klauck	A strong direct product theorem for disjointness.	STOC	2010	DBLP DOI BibTeX RDF	communication-space tradeoffs, disjointness problem, lower bounds, communication complexity, complexity theory, direct product theorems
2	Andrew Chi-Chih Yao	Communication Complexity and Its Applications.	FAW	2009	DBLP DOI BibTeX RDF
2	Jérémie Roland, Mario Szegedy	Amortized Communication Complexity of Distributions.	ICALP	2009	DBLP DOI BibTeX RDF
2	Jan Draisma, Eyal Kushilevitz, Enav Weinreb	Partition Arguments in Multiparty Communication Complexity.	ICALP	2009	DBLP DOI BibTeX RDF
2	Marc Kaplan, Sophie Laplante	Kolmogorov Complexity and Combinatorial Methods in Communication Complexity.	TAMC	2009	DBLP DOI BibTeX RDF
2	Julien Degorre, Marc Kaplan, Sophie Laplante, Jérémie Roland	The Communication Complexity of Non-signaling Distributions.	MFCS	2009	DBLP DOI BibTeX RDF
2	Florian Kerschbaum, Daniel Dahlmeier, Axel Schröpfer, Debmalya Biswas	On the practical importance of communication complexity for secure multi-party computation protocols.	SAC	2009	DBLP DOI BibTeX RDF	synchronization, performance measurement, experimentation, secure multi-party computation
2	Paul Beame, Dang-Trinh Huynh-Ngoc	Multiparty Communication Complexity and Threshold Circuit Size of AC^0.	FOCS	2009	DBLP DOI BibTeX RDF	lower bounds, communication complexity, constant-depth circuits
2	Bogdan S. Chlebus, Dariusz R. Kowalski, Michal Strojnowski	Fast scalable deterministic consensus for crash failures.	PODC	2009	DBLP DOI BibTeX RDF	bit communication complexity, graph expansion, fault tolerance, scalability, message passing, consensus, synchrony
2	Bogdan S. Chlebus, Dariusz R. Kowalski	Locally scalable randomized consensus for synchronous crash failures.	SPAA	2009	DBLP DOI BibTeX RDF	bit communication complexity, graph expansion, fault tolerance, scalability, lower bound, message passing, randomization, consensus, synchrony
2	Rahul Jain, Jaikumar Radhakrishnan, Pranab Sen	A property of quantum relative entropy with an application to privacy in quantum communication.	J. ACM	2009	DBLP DOI BibTeX RDF	quantum communication complexity, Privacy, quantum information theory
2	Dana Pardubská, Martin Plátek, Friedrich Otto	Parallel Communicating Grammar Systems with Regular Control.	CAI	2009	DBLP DOI BibTeX RDF	parallel communicating grammar system, regular control, bounded communication complexity, freely rewriting restarting automaton
2	François Le Gall	Exponential Separation of Quantum and Classical Online Space Complexity.	Theory Comput. Syst.	2009	DBLP DOI BibTeX RDF	Online space complexity, Quantum computation, Communication complexity
2	Daniele Micciancio, Saurabh Panjwani	Optimal communication complexity of generic multicast key distribution.	IEEE/ACM Trans. Netw.	2008	DBLP DOI BibTeX RDF	nested encryption, security, multicast, lower bounds, secret sharing, key distribution
2	Dima Grigoriev	Probabilistic Communication Complexity Over The Reals.	Computational Complexity	2008	DBLP DOI BibTeX RDF	Subject classification, 68W40
2	N. E. Venkatesan, Tarun Agarwal, P. Vijay Kumar	On the Average Case Communication Complexity for Detection in Sensor Networks.	DCOSS	2008	DBLP DOI BibTeX RDF
2	Takashi Tanaka, Cedric Langbort	Communication complexity in the distributed design of linear quadratic optimal controllers.	CDC	2008	DBLP DOI BibTeX RDF
2	Xiaofei Liu, Song Guo, Abdulmotaleb El-Saddik	Communication Complexity Evaluation for Longest-Lived Directional Multicasting in WANETs.	ICC	2008	DBLP DOI BibTeX RDF
2	Anil Ada	On the Non-deterministic Communication Complexity of Regular Languages.	Developments in Language Theory	2008	DBLP DOI BibTeX RDF
2	Markus Bläser, Elias Vicari	Distributed Algorithmic Mechanism Design and Algebraic Communication Complexity.	SAGT	2008	DBLP DOI BibTeX RDF
2	Iftach Haitner, Jonathan J. Hoch, Gil Segev	A Linear Lower Bound on the Communication Complexity of Single-Server Private Information Retrieval.	TCC	2008	DBLP DOI BibTeX RDF
2	Seiichiro Tani, Masaki Nakanishi, Shigeru Yamashita	Multi-party Quantum Communication Complexity with Routed Messages.	COCOON	2008	DBLP DOI BibTeX RDF
2	Hermann Gruber, Jan Johannsen	Optimal Lower Bounds on Regular Expression Size Using Communication Complexity.	FoSSaCS	2008	DBLP DOI BibTeX RDF
2	Scott Aaronson, Avi Wigderson	Algebrization: a new barrier in complexity theory.	STOC	2008	DBLP DOI BibTeX RDF	communication complexity, oracles, arithmetization, interactive proofs, query complexity, low-degree polynomials
2	Amit Chakrabarti, Graham Cormode, Andrew McGregor	Robust lower bounds for communication and stream computation.	STOC	2008	DBLP DOI BibTeX RDF	lower bounds, data streams, communication complexity
2	Alexander A. Sherstov	The pattern matrix method for lower bounds on quantum communication.	STOC	2008	DBLP DOI BibTeX RDF	approximate degree of boolean functions, bounded-error communication, quantum communication complexity, lower bounds
2	Yefim Dinitz, Shlomo Moran, Sergio Rajsbaum	Bit complexity of breaking and achieving symmetry in chains and rings.	J. ACM	2008	DBLP DOI BibTeX RDF	bit complexity, processor chain, processor ring, symmetric synchronous execution, Distributed computing, lower bounds, consensus, communication complexity, leader election, communication cost, message complexity, tight bound
2	Anne Broadbent, Alain Tapp	Can quantum mechanics help distributed computing?	SIGACT News	2008	DBLP DOI BibTeX RDF	pseudo-telepathy, quantum games, simulation of entanglement, communication complexity
2	Troy Lee, Adi Shraibman	Disjointness Is Hard in the Multi-party Number-on-the-Forehead Model.	IEEE Conference on Computational Complexity	2008	DBLP DOI BibTeX RDF	multiparty communication complexity, disjointness, lower bounds
2	Troy Lee, Adi Shraibman, Robert Spalek	A Direct Product Theorem for Discrepancy.	IEEE Conference on Computational Complexity	2008	DBLP DOI BibTeX RDF	direct sum theorems, factorization norms, communication complexity, discrepancy, direct product theorems
2	Boaz Patt-Shamir, Allon Shafrir	Approximate distributed top- k queries.	Distributed Computing	2008	DBLP DOI BibTeX RDF	Sensor networks, Distributed algorithms, Communication complexity, Random sampling, Aggregate queries
2	Paul Beame, Matei David, Toniann Pitassi, Philipp Woelfel	Separating Deterministic from Nondeterministic NOF Multiparty Communication Complexity.	ICALP	2007	DBLP DOI BibTeX RDF
2	Kazuo Iwama, Harumichi Nishimura, Rudy Raymond, Shigeru Yamashita	Unbounded-Error One-Way Classical and Quantum Communication Complexity.	ICALP	2007	DBLP DOI BibTeX RDF
2	Ashley Montanaro, Andreas Winter	A Lower Bound on Entanglement-Assisted Quantum Communication Complexity.	ICALP	2007	DBLP DOI BibTeX RDF
2	Iordanis Kerenidis	Quantum Multiparty Communication Complexity and Circuit Lower Bounds.	TAMC	2007	DBLP DOI BibTeX RDF
2	Arkadev Chattopadhyay, Andreas Krebs, Michal Koucký, Mario Szegedy, Pascal Tesson, Denis Thérien	Languages with Bounded Multiparty Communication Complexity.	STACS	2007	DBLP DOI BibTeX RDF
2	Nan Zhang	On the Communication Complexity of Privacy-Preserving Information Sharing Protocols.	ISI	2007	DBLP DOI BibTeX RDF
2	Kazuo Iwama, Harumichi Nishimura, Rudy Raymond, Shigeru Yamashita	Unbounded-Error Classical and Quantum Communication Complexity.	ISAAC	2007	DBLP DOI BibTeX RDF
2	Prahladh Harsha, Rahul Jain, David A. McAllester, Jaikumar Radhakrishnan	The Communication Complexity of Correlation.	IEEE Conference on Computational Complexity	2007	DBLP DOI BibTeX RDF
2	Dmitry Gavinsky, Julia Kempe, Iordanis Kerenidis, Ran Raz, Ronald de Wolf	Exponential separations for one-way quantum communication complexity, with applications to cryptography.	STOC	2007	DBLP DOI BibTeX RDF	cryptography, communication complexity, quantum
2	Alexander A. Sherstov	Separating AC0 from depth-2 majority circuits.	STOC	2007	DBLP DOI BibTeX RDF	AC0, communication complexity, discrepancy, threshold circuits
2	Rafail Ostrovsky, Yuval Rabani	Low distortion embeddings for edit distance.	J. ACM	2007	DBLP DOI BibTeX RDF	Pattern matching, sketching, communication complexity, edit distance, dimension reduction, nearest neighbor search, metric embeddings, Levenshtein distance, computations on discrete structures
2	Matthew K. Franklin, Mark Gondree, Payman Mohassel	Multi-party Indirect Indexing and Applications.	ASIACRYPT	2007	DBLP DOI BibTeX RDF	oblivious RAM machine, communication complexity, secure multiparty computation, privacy-preserving protocols
2	Jun Tarui	Finding a Duplicate and a Missing Item in a Stream.	TAMC	2007	DBLP DOI BibTeX RDF	finding duplicate, finding missing item, communication complexity, proof complexity, Data stream algorithm, pigeonhole principle
2	Paul Beame, Toniann Pitassi, Nathan Segerlind, Avi Wigderson	A Strong Direct Product Theorem for Corruption and the Multiparty Communication Complexity of Disjointness.	Computational Complexity	2006	DBLP DOI BibTeX RDF	06D15, 68Q17, 68Q15, 06E30, Subject classification. 68Q10
2	François Le Gall	Quantum Weakly Nondeterministic Communication Complexity.	MFCS	2006	DBLP DOI BibTeX RDF
2	Richard Beigel, William I. Gasarch, James Glenn	The Multiparty Communication Complexity of Exact-T: Improved Bounds and New Problems.	MFCS	2006	DBLP DOI BibTeX RDF
2	Martin Hirt, Jesper Buus Nielsen	Robust Multiparty Computation with Linear Communication Complexity.	CRYPTO	2006	DBLP DOI BibTeX RDF
2	Boaz Patt-Shamir, Allon Shafrir	Approximate Top-k Queries in Sensor Networks.	SIROCCO	2006	DBLP DOI BibTeX RDF
2	Matthias Fitzi, Martin Hirt	Optimally efficient multi-valued byzantine agreement.	PODC	2006	DBLP DOI BibTeX RDF	cryptographic security, communication complexity, byzantine agreement, information-theoretic security
2	François Le Gall	Exponential separation of quantum and classical online space complexity.	SPAA	2006	DBLP DOI BibTeX RDF	quantum computation, communication complexity, online, space complexity, streaming algorithms
2	Pascal Tesson, Denis Thérien	Complete Classifications for the Communication Complexity of Regular Languages.	Theory Comput. Syst.	2005	DBLP DOI BibTeX RDF
2	Paul Beame, Toniann Pitassi, Nathan Segerlind	Lower Bounds for Lovász-Schrijver Systems and Beyond Follow from Multiparty Communication Complexity.	ICALP	2005	DBLP DOI BibTeX RDF
2	Pascal Tesson, Denis Thérien	Restricted Two-Variable Sentences, Circuits and Communication Complexity.	ICALP	2005	DBLP DOI BibTeX RDF
2	Jeff Ford, Anna Gál	Hadamard Tensors and Lower Bounds on Multiparty Communication Complexity.	ICALP	2005	DBLP DOI BibTeX RDF
2	Andrew Chi-Chih Yao	On the Communication Complexity of Co-linearity Problems.	MFCS	2005	DBLP DOI BibTeX RDF
2	Adán Cabello	Communication Complexity as a Principle of Quantum Mechanics.	UC	2005	DBLP DOI BibTeX RDF
2	Martin Hirt, Jesper Buus Nielsen	Upper Bounds on the Communication Complexity of Optimally Resilient Cryptographic Multiparty Computation.	ASIACRYPT	2005	DBLP DOI BibTeX RDF
2	Paul Beame, Toniann Pitassi, Nathan Segerlind, Avi Wigderson	A Direct Sum Theorem for Corruption and the Multiparty NOF Communication Complexity of Set Disjointness.	IEEE Conference on Computational Complexity	2005	DBLP DOI BibTeX RDF
2	Yaoyun Shi	Tensor norms and the classical communication complexity of nonlocal quantum measurement.	STOC	2005	DBLP DOI BibTeX RDF	bell inequality, classical simulation, fourier sampling problem, quantum entanglement, tensor norms, communication complexity
2	Harry Buhrman, Hartmut Klauck, Nikolai K. Vereshchagin, Paul M. B. Vitányi	Individual Communication Complexity: Extended Abstract.	STACS	2004	DBLP DOI BibTeX RDF
2	Gilles Brassard	Quantum Communication Complexity: A Survey.	ISMVL	2004	DBLP DOI BibTeX RDF
2	Vincent Conitzer, Tuomas Sandholm	Communication complexity as a lower bound for learning in games.	ICML	2004	DBLP DOI BibTeX RDF
2	Heeyoul Kim, Jaewon Lee, Hyunsoo Yoon, Jung Wan Cho	Secure Group Communication with Low Communication Complexity.	PDCAT	2004	DBLP DOI BibTeX RDF	Security, Secure Group Communication, Networking and Communications
2	Andris Ambainis, Ke Yang	Towards the Classical Communication Complexity of Entanglement Distillation Protocols with Incomplete Information.	IEEE Conference on Computational Complexity	2004	DBLP DOI BibTeX RDF
2	Kirill Levchenko, Ramamohan Paturi, George Varghese	On the difficulty of scalably detecting network attacks.	ACM Conference on Computer and Communications Security	2004	DBLP DOI BibTeX RDF	communication complexity, network intrusion detection
2	Boaz Patt-Shamir	A note on efficient aggregate queries in sensor networks.	PODC	2004	DBLP DOI BibTeX RDF	sensor networks, communication complexity, median
2	Vince Grolmusz, Gábor Tardos	A Note on Non-Deterministic Communication Complexity with Few Witnesses.	Theory Comput. Syst.	2003	DBLP DOI BibTeX RDF
2	Pavol Purcz	Asymptotical Behaviour of the Communication Complexity of One Parallel Algorithm.	PPAM	2003	DBLP DOI BibTeX RDF