Search results for "lower bounds"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
4	Monika Rauch Henzinger, Michael L. Fredman	Lower Bounds for Fully Dynamic Connectivity Problems in Graphs.	Algorithmica	1998	DBLP DOI BibTeX RDF	Dynamic planarity testing, Dynamic connectivity testing, Dynamic planarity testing, Dynamic connectivity testing, Lower bounds, Lower bounds, Key words, Cell probe model, Cell probe model
3	Sunil Arya, David M. Mount, Jian Xia	Tight lower bounds for halfspace range searching.	Symposium on Computational Geometry	2010	DBLP DOI BibTeX RDF	lower bounds, range searching, idempotence
3	Ran Raz	Tensor-rank and lower bounds for arithmetic formulas.	STOC	2010	DBLP DOI BibTeX RDF	homogenous circuits, multilinear circuits, tensor rank, lower bounds, arithmetic circuits
3	Mihai Patrascu	Towards polynomial lower bounds for dynamic problems.	STOC	2010	DBLP DOI BibTeX RDF	3SUM, lower bounds, dynamic data structures
3	Yehuda Lindell	Lower Bounds and Impossibility Results for Concurrent Self Composition.	J. Cryptology	2008	DBLP DOI BibTeX RDF	Self and general composition, Non-black-box and black-box simulation, Lower bounds, Secure computation, Protocol composition, Impossibility results
3	Per Austrin, Gunnar Kreitz	Lower Bounds for Subset Cover Based Broadcast Encryption.	AFRICACRYPT	2008	DBLP DOI BibTeX RDF	Subset Cover, lower bounds, Broadcast Encryption, key revocation
3	Eric Allender, Michal Koucký	Amplifying Lower Bounds by Means of Self-Reducibility.	IEEE Conference on Computational Complexity	2008	DBLP DOI BibTeX RDF	self-reducibility, lower bounds, circuit complexity
3	Ran Raz	Elusive functions and lower bounds for arithmetic circuits.	STOC	2008	DBLP DOI BibTeX RDF	bounded depth circuits, lower bounds, arithmetic circuits, circuit complexity
3	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
3	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
3	Adam R. Klivans, Alexander A. Sherstov	Unconditional lower bounds for learning intersections of halfspaces.	Machine Learning	2007	DBLP DOI BibTeX RDF	Intersections of halfspaces, Halfspace learning, SQ learning, Lower bounds for learning, Harmonic sieve, PAC learning, Query learning, Statistical queries, Polynomial threshold functions
3	Hoeteck Wee	Lower Bounds for Non-interactive Zero-Knowledge.	TCC	2007	DBLP DOI BibTeX RDF	set-up assumptions, lower bounds, Non-interactive zero-knowledge
3	Maurice J. Jansen, Kenneth W. Regan	"Resistant" Polynomials and Stronger Lower Bounds for Depth-Three Arithmetical Formulas.	COCOON	2007	DBLP DOI BibTeX RDF	constant depth formulas, Computational complexity, lower bounds, arithmetical circuits, partial derivatives
3	Mihai Patrascu	Lower bounds for 2-dimensional range counting.	STOC	2007	DBLP DOI BibTeX RDF	cell-probe complexity, orthogonal range queries, lower bounds
3	Rahul Santhanam	Circuit lower bounds for Merlin-Arthur classes.	STOC	2007	DBLP DOI BibTeX RDF	Merlin-Arthur games, average-case lower bounds, circuit lower bounds, advice, pseudo-random generators
3	Mark Nicholas Charles Rhodes	Rank Lower Bounds for the Sherali-Adams Operator.	CiE	2007	DBLP DOI BibTeX RDF	Lift and Project Proof Systems, Rank Lower Bounds, Sherali-Adams Relaxation, Propositional Proof Complexity
3	Daiyuan Peng, Pingzhi Fan, Moon Ho Lee	Lower bounds on the periodic Hamming correlations of frequency hopping sequences with low hit zone.	Science in China Series F: Information Sciences	2006	DBLP DOI BibTeX RDF	frequency hopping sequences, Hamming correlation, Lempel-Greenberger bounds, low hit zone, no hit zone, lower bounds
3	Lance Fortnow, Richard J. Lipton, Dieter van Melkebeek, Anastasios Viglas	Time-space lower bounds for satisfiability.	J. ACM	2005	DBLP DOI BibTeX RDF	Complexity of satisfiability, time-space lower bounds
3	Peter Bürgisser, Martin Lotz	Lower bounds on the bounded coefficient complexity of bilinear maps.	J. ACM	2004	DBLP DOI BibTeX RDF	bilinear circuits, lower bounds, Algebraic complexity, singular values
3	Scott Aaronson, Yaoyun Shi	Quantum lower bounds for the collision and the element distinctness problems.	J. ACM	2004	DBLP DOI BibTeX RDF	element distinctness, polynomial method, quantum lower bounds, quantum computing, Collision
3	Vineet Bafna, Vikas Bansal	The Number of Recombination Events in a Sample History: Conflict Graph and Lower Bounds.	IEEE/ACM Trans. Comput. Biology Bioinform.	2004	DBLP DOI BibTeX RDF	ancestral recombination graph, lower bounds, NP-completeness, Recombination, haplotypes, conflict graph, phylogenetic networks
3	Oliver Kullmann	Upper and Lower Bounds on the Complexity of Generalised Resolution and Generalised Constraint Satisfaction Problems.	Ann. Math. Artif. Intell.	2004	DBLP DOI BibTeX RDF	satisfiability problem (SAT), systems with partial instantiation, generalised resolution, lower bounds for resolution, upper bounds for SAT algorithms, automatisation of proof systems, generalised input resolution, generalised width restricted resolution, induced width of constraint satisfaction problems, constraint satisfaction problems, propositional logic, polynomial time hierarchies
3	Mihai Patrascu, Erik D. Demaine	Lower bounds for dynamic connectivity.	STOC	2004	DBLP DOI BibTeX RDF	cell-probe complexity, dynamic connectivity, dynamic graph problems, lower bounds for data structures, partial sums problem
3	Marco A. Boschetti, Aristide Mingozzi	The two-dimensional finite bin packing problem. Part I: New lower bounds for the oriented case.	4OR	2003	DBLP DOI BibTeX RDF	Lower Bounds, Combinatorial Optimization, Cutting and Packing
3	Valentine Kabanets, Russell Impagliazzo	Derandomizing polynomial identity tests means proving circuit lower bounds.	STOC	2003	DBLP DOI BibTeX RDF	BPP, NEXP, circuit lower bounds, derandomization, polynomial identity testing
3	Rosario Gennaro, Yael Gertner, Jonathan Katz	Lower bounds on the efficiency of encryption and digital signature schemes.	STOC	2003	DBLP DOI BibTeX RDF	lower bounds, digital signatures, encryption, black-box
3	Ziv Bar-Yossef	Sampling lower bounds via information theory.	STOC	2003	DBLP DOI BibTeX RDF	lower bounds, query complexity, Jensen-Shannon divergence
3	Anna Gál, Adi Rosén	Lower bounds on the amount of randomness in private computation.	STOC	2003	DBLP DOI BibTeX RDF	lower bounds, randomness, private computation
3	Amir M. Ben-Amram, Zvi Galil	Lower Bounds for Dynamic Data Structures on Algebraic RAMs.	Algorithmica	2002	DBLP DOI BibTeX RDF	Cell-probe lower bounds, Dynamic prefix sum, Union-find, Random access machine
3	Peter Brucker, Sigrid Knust	Lower Bounds for Scheduling a Single Robot in a Job-Shop Environment.	Annals OR	2002	DBLP DOI BibTeX RDF	traveling salesman problem with time windows, scheduling, lower bounds, constraint propagation, column generation, time-lags
3	Dino Ahr, Gerhard Reinelt	New Heuristics and Lower Bounds for the Min-Max k -Chinese Postman Problem.	ESA	2002	DBLP DOI BibTeX RDF	Min-Max Optimization, Heuristics, Lower Bounds, Chinese Postman Problem, Arc Routing
3	Roberto Montemanni, D. H. Smith, Stuart M. Allen	Lower Bounds for Fixed Spectrum Frequency Assignment.	Annals OR	2001	DBLP DOI BibTeX RDF	radio frequency assignment, fixed spectrum problems, lower bounds
3	Anna Gál	A characterization of span program size and improved lower bounds for monotone span programs.	Computational Complexity	2001	DBLP DOI BibTeX RDF	Span programs, Boolean formula size, secret sharing..¶ Subject classification. 68Q15, lower bounds, 94C10
3	Christer Berg, Staffan Ulfberg	Symmetric Approximation Arguments for Monotone Lower Bounds Without Sunflowers.	Computational Complexity	1999	DBLP DOI BibTeX RDF	lower bounds, Circuit complexity, monotone circuits
3	Sascha Ott	Lower Bounds for Approximating Shortest Superstrings over an Alphabet of Size 2.	WG	1999	DBLP DOI BibTeX RDF	Superstrings, lower bounds, approximability, APX-hardness
3	Jacobo Torán	Lower Bounds for Space in Resolution.	CSL	1999	DBLP DOI BibTeX RDF	lower bounds, Resolution, space, complexity measures, pebbling game
3	Ueli M. Maurer, Stefan Wolf	Lower Bounds on Generic Algorithms in Groups.	EUROCRYPT	1998	DBLP DOI BibTeX RDF	Diffie-Hellman protocol, roots in finite groups, complexity, lower bounds, discrete logarithms, generic algorithms
3	Dima Grigoriev	Tseitin's Tautologies and Lower Bounds for Nullstellensatz Proofs.	FOCS	1998	DBLP DOI BibTeX RDF	Nullstellensatz proofs, Tseitin's tautologies, lower bounds, expander
3	Marc Fischlin	Lower Bounds for the Signature Size of Incremental Schemes.	FOCS	1997	DBLP DOI BibTeX RDF	incremental schemes, signature size, substitution attacks, single block replacement, lower bounds, security of data
3	Stasys Jukna	Finite Limits and Monotone Computations: The Lower Bounds Criterion. (PDF / PS)	IEEE Conference on Computational Complexity	1997	DBLP DOI BibTeX RDF	real gates, lower bounds, threshold gates, monotone circuits
3	Paul Beame, Toniann Pitassi	Simplified and Improved Resolution Lower Bounds.	FOCS	1996	DBLP DOI BibTeX RDF	resolution lower bounds, randomly generated formulas, random formulas, randomly chosen 3-CNF formula, lower bounds, computability, pigeonhole principle
3	Sieteng Soh, Suresh Rai, Jerry L. Trahan	Improved Lower Bounds on the Reliability of Hypercube Architectures.	IEEE Trans. Parallel Distrib. Syst.	1994	DBLP DOI BibTeX RDF	Boolean n-cube, structural-reliability models, tighter bounds, time O(n/sup 2/), reliability bounds, computational complexity, reliability, reliability, parallel architectures, lower bounds, fault tolerant computing, hypercube, hypercube networks, spanning trees, network reliability, node failure, path generation, hypercube topology, terminal reliability, hypercube architecture
3	Karl R. Abrahamson, Andrew Adler, Lisa Higham, David G. Kirkpatrick	Tight Lower Bounds for Probabilistic Solitude Verification on Anonymous Rings.	J. ACM	1994	DBLP DOI BibTeX RDF	Solitude Verification, anonymous ring, asynchronous unidirectional ring, bit complexity, lower bounds, nondeterminism, Leader Election
3	Christine Rüb	Lower Bounds for Merging on the Hypercube.	CIAC	1994	DBLP DOI BibTeX RDF	Lower bounds, Hypercube, Sorting, Merging
2	Peyman Afshani, Lars Arge, Kasper Dalgaard Larsen	Orthogonal range reporting: query lower bounds, optimal structures in 3-d, and higher-dimensional improvements.	Symposium on Computational Geometry	2010	DBLP DOI BibTeX RDF	orthogonal range reporting, pointer machine, data structures, lower bounds
2	Laura Grigori, Pierre-Yves David, James Demmel, Sylvain Peyronnet	Brief announcement: Lower bounds on communication for sparse Cholesky factorization of a model problem.	SPAA	2010	DBLP DOI BibTeX RDF	communication bounds, sparse Cholesky
2	Eric Blais, Ryan O'Donnell	Lower Bounds for Testing Function Isomorphism.	IEEE Conference on Computational Complexity	2010	DBLP DOI BibTeX RDF	lower bounds, Boolean functions, property testing
2	Hagit Attiya	The inherent complexity of transactional memory and what to do about it.	PODC	2010	DBLP DOI BibTeX RDF	mini-transactions, lower bounds, transactional memory
2	Pavel Hrubes, Avi Wigderson, Amir Yehudayoff	Non-commutative circuits and the sum-of-squares problem.	STOC	2010	DBLP DOI BibTeX RDF	lower bounds, algebraic complexity
2	Mathieu Bouchard, Alain Hertz, Guy Desaulniers	Lower bounds and a tabu search algorithm for the minimum deficiency problem.	J. Comb. Optim.	2009	DBLP DOI BibTeX RDF	Minimum deficiency problem, Tabu search, Edge coloring
2	János Balogh, József Békési, Gábor Galambos, Mihály Csaba Markót	Improved lower bounds for semi-online bin packing problems.	Computing	2009	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000) 68Q25, 68W40, 68W25
2	Martin Grohe, André Hernich, Nicole Schweikardt	Lower bounds for processing data with few random accesses to external memory.	J. ACM	2009	DBLP DOI BibTeX RDF	real-time data, XML, Complexity, query processing, data streams, query optimization, semi-structured data
2	Parastoo Sadeghi, Pascal O. Vontobel, Ramtin Shams	Optimization of Information Rate Upper and Lower Bounds for Channels With Memory.	IEEE Transactions on Information Theory	2009	DBLP DOI BibTeX RDF
2	Maurice J. Jansen	Lower Bounds for the Determinantal Complexity of Explicit Low Degree Polynomials.	CSR	2009	DBLP DOI BibTeX RDF	elementary symmetric polynomial, Computational complexity, determinant, arithmetical circuits, permanent
2	Toniann Pitassi, Nathan Segerlind	Exponential lower bounds and integrality gaps for tree-like Lovász-Schrijver procedures.	SODA	2009	DBLP DOI BibTeX RDF
2	Alexander Golynski	Cell probe lower bounds for succinct data structures.	SODA	2009	DBLP DOI BibTeX RDF
2	Timothy M. Chan	Comparison-based time-space lower bounds for selection.	SODA	2009	DBLP DOI BibTeX RDF
2	Harry Buhrman, Lance Fortnow, Rahul Santhanam	Unconditional Lower Bounds against Advice.	ICALP	2009	DBLP DOI BibTeX RDF
2	Boris Bukh, Jirí Matousek, Gabriel Nivasch	Lower bounds for weak epsilon-nets and stair-convexity.	Symposium on Computational Geometry	2009	DBLP DOI BibTeX RDF	inverse ackermann function, selection lemma, stair-convexity, weak epsilon-net
2	Martin Dietzfelbinger, Philipp Woelfel	Brief announcement: tight lower bounds for greedy routing in uniform small world rings.	PODC	2009	DBLP DOI BibTeX RDF	peer-to-peer, lower bound, random graphs, small worlds, greedy routing
2	Donald Stanley, Boting Yang	Lower Bounds on Fast Searching.	ISAAC	2009	DBLP DOI BibTeX RDF
2	Ke Yi	Dynamic indexability and lower bounds for dynamic one-dimensional range query indexes.	PODS	2009	DBLP DOI BibTeX RDF	lower bound, indexability, dynamization, range query
2	Orna Kupferman, Nir Piterman	Lower Bounds on Witnesses for Nonemptiness of Universal Co-Büchi Automata.	FOSSACS	2009	DBLP DOI BibTeX RDF
2	José Luis Montaña, Cruz E. Borges	Lower Bounds for Approximation of Some Classes of Lebesgue Measurable Functions by Sigmoidal Neural Networks.	IWANN	2009	DBLP DOI BibTeX RDF	Mathematics of Neural Networks, Approximation Theory
2	Emanuele Viola	Bit-probe lower bounds for succinct data structures.	STOC	2009	DBLP DOI BibTeX RDF	bit-probe, cell-probe, logarithmic form, ternary value, lower bound, dictionary, succinct data structure, membership query
2	Peyman Afshani, Chris H. Hamilton, Norbert Zeh	Cache-oblivious range reporting with optimal queries requires superlinear space.	Symposium on Computational Geometry	2009	DBLP DOI BibTeX RDF	data structures, lower bounds, memory hierarchies, range searching, cache-obliviousness
2	Andrea Vattani	k-means requires exponentially many iterations even in the plane.	Symposium on Computational Geometry	2009	DBLP DOI BibTeX RDF	lower bounds, k-means
2	John R. Douceur, James W. Mickens, Thomas Moscibroda, Debmalya Panigrahi	Brief announcement: collaborative measurement of upload speeds in P2P systems.	PODC	2009	DBLP DOI BibTeX RDF	lower bounds, P2P systems, bandwidth estimation
2	Fabian Kuhn, Nancy A. Lynch, Calvin C. Newport	Brief announcement: hardness of broadcasting in wireless networks with unreliable communication.	PODC	2009	DBLP DOI BibTeX RDF	lower bounds, broadcast
2	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
2	Hagit Attiya, Rachid Guerraoui, Danny Hendler, Petr Kuznetsov	The complexity of obstruction-free implementations.	J. ACM	2009	DBLP DOI BibTeX RDF	perturbable objects, solo-fast implementations, step contention, lower bounds, Shared memory, memory contention
2	Ran Raz	Multi-linear formulas for permanent and determinant are of super-polynomial size.	J. ACM	2009	DBLP DOI BibTeX RDF	arithmetic formulas, lower bounds, circuit complexity, algebraic complexity
2	Lou van den Dries, Yiannis N. Moschovakis	Arithmetic complexity.	ACM Trans. Comput. Log.	2009	DBLP DOI BibTeX RDF	Lower bounds for arithmetical problems, coprimeness, greatest common divisor, recursive programs
2	Andreas Haeberlen, Petr Kuznetsov	The Fault Detection Problem.	OPODIS	2009	DBLP DOI BibTeX RDF	fault detection problem, lower bounds, message complexity, Fault classes
2	Andris Ambainis, Robert Spalek, Ronald de Wolf	A New Quantum Lower Bound Method, with Applications to Direct Product Theorems and Time-Space Tradeoffs.	Algorithmica	2009	DBLP DOI BibTeX RDF	Quantum lower bounds, Boolean functions, Quantum computing, Quantum algorithms, Time-space tradeoffs
2	Damien Woods, J. Paul Gibson	Lower bounds on the computational power of an optical model of computation.	Natural Computing	2008	DBLP DOI BibTeX RDF
2	Hans L. Bodlaender, Alexander Grigoriev, Arie M. C. A. Koster	Treewidth Lower Bounds with Brambles.	Algorithmica	2008	DBLP DOI BibTeX RDF	Bramble, Grid minor, Approximation algorithm, Lower bound, Planar graph, Treewidth
2	Mihailo Stojnic, Haris Vikalo, Babak Hassibi	Speeding up the Sphere Decoder With Hinfty and SDP Inspired Lower Bounds.	IEEE Transactions on Signal Processing	2008	DBLP DOI BibTeX RDF
2	Laurent Alonso, Edward M. Reingold	Average-case lower bounds for the plurality problem.	ACM Transactions on Algorithms	2008	DBLP DOI BibTeX RDF	majority problem, plurality problem, Algorithm analysis
2	Yeow Meng Chee, San Ling	Improved Lower Bounds for Constant GC-Content DNA Codes.	IEEE Transactions on Information Theory	2008	DBLP DOI BibTeX RDF
2	Stefan Wolf, Jürg Wullschleger	New Monotones and Lower Bounds in Unconditional Two-Party Computation.	IEEE Transactions on Information Theory	2008	DBLP DOI BibTeX RDF
2	Kaoru Kurosawa, Wataru Kishimoto, Takeshi Koshiba	A Combinatorial Approach to Deriving Lower Bounds for Perfectly Secure Oblivious Transfer Reductions.	IEEE Transactions on Information Theory	2008	DBLP DOI BibTeX RDF
2	Pietro Simone Oliveto, Carsten Witt	Simplified Drift Analysis for Proving Lower Bounds in Evolutionary Computation.	PPSN	2008	DBLP DOI BibTeX RDF
2	Olivier Teytaud, Hervé Fournier	Lower Bounds for Evolution Strategies Using VC-Dimension.	PPSN	2008	DBLP DOI BibTeX RDF	Convergence ratio, Sign conditions, Evolution Strategies, VC-dimension
2	Eric Allender	Cracks in the Defenses: Scouting Out Approaches on Circuit Lower Bounds.	CSR	2008	DBLP DOI BibTeX RDF
2	Dmitriy Yu. Cherukhin	Lower Bounds for Depth-2 and Depth-3 Boolean Circuits with Arbitrary Gates.	CSR	2008	DBLP DOI BibTeX RDF	complexity, lower bound, Boolean function, circuit, depth, cyclic convolution
2	Pascal Koiran, Jürgen Landes, Natacha Portier, Penghui Yao	Adversary Lower Bounds for Nonadaptive Quantum Algorithms.	WoLLIC	2008	DBLP DOI BibTeX RDF
2	Mark Mercer	Lower Bounds for Generalized Quantum Finite Automata.	LATA	2008	DBLP DOI BibTeX RDF
2	Sudipto Guha, Andrew McGregor	Tight Lower Bounds for Multi-pass Stream Computation Via Pass Elimination.	ICALP	2008	DBLP DOI BibTeX RDF
2	Nitin Saxena	Diagonal Circuit Identity Testing and Lower Bounds.	ICALP	2008	DBLP DOI BibTeX RDF	identity testing, depth 3, depth 4, lower bounds, determinant, arithmetic circuit, permanent
2	Maurice J. Jansen	Lower Bounds for Syntactically Multilinear Algebraic Branching Programs.	MFCS	2008	DBLP DOI BibTeX RDF	multilinear polynomials, algebraic branching programs, Computational complexity, lower bounds, arithmetical circuits
2	J. Ian Munro	Lower Bounds for Succinct Data Structures.	CPM	2008	DBLP DOI BibTeX RDF
2	Andy Rupp, Gregor Leander, Endre Bangerter, Alexander W. Dent, Ahmad-Reza Sadeghi	Sufficient Conditions for Intractability over Black-Box Groups: Generic Lower Bounds for Generalized DL and DH Problems.	ASIACRYPT	2008	DBLP DOI BibTeX RDF	Generic Group Model, Hardness Conditions, Lower Bounds, Straight-Line Programs
2	Ittai Abraham, Danny Dolev, Joseph Y. Halpern	Lower Bounds on Implementing Robust and Resilient Mediators.	TCC	2008	DBLP DOI BibTeX RDF
2	Vahab S. Mirrokni, Michael Schapira, Jan Vondrák	Tight information-theoretic lower bounds for welfare maximization in combinatorial auctions.	ACM Conference on Electronic Commerce	2008	DBLP DOI BibTeX RDF	approximation algorithms, combinatorial auctions
2	Hang Dinh, Alexander Russell	Quantum and Randomized Lower Bounds for Local Search on Vertex-Transitive Graphs.	APPROX-RANDOM	2008	DBLP DOI BibTeX RDF
2	Vikraman Arvind, Partha Mukhopadhyay	Derandomizing the Isolation Lemma and Lower Bounds for Circuit Size.	APPROX-RANDOM	2008	DBLP DOI BibTeX RDF
2	Yefim Dinitz, Michael Elkin, Shay Solomon	Shallow-Low-Light Trees, and Tight Lower Bounds for Euclidean Spanners.	FOCS	2008	DBLP DOI BibTeX RDF
2	Rina Panigrahy, Kunal Talwar, Udi Wieder	A Geometric Approach to Lower Bounds for Approximate Near-Neighbor Search and Partial Match.	FOCS	2008	DBLP DOI BibTeX RDF
2	Zoya Svitkina, Lisa Fleischer	Submodular Approximation: Sampling-based Algorithms and Lower Bounds.	FOCS	2008	DBLP DOI BibTeX RDF