## Stem lower$ (all stems)

### 314 papers:

- DATE-2015-KaneYHSS #architecture #interface #realtime
- A neural machine interface architecture for real-time artificial lower limb control (JK, QY, RH, WS, MS), pp. 633–636.
- STOC-2015-AbdullahV #bound #difference
- A Directed Isoperimetric Inequality with application to Bregman Near Neighbor Lower Bounds (AA, SV), pp. 509–518.
- STOC-2015-BarakCK #bound #independence
- Sum of Squares Lower Bounds from Pairwise Independence (BB, SOC, PKK), pp. 97–106.
- STOC-2015-LarsenNN #adaptation #algorithm #bound #streaming
- Time Lower Bounds for Nonadaptive Turnstile Streaming Algorithms (KGL, JN, HLN), pp. 803–812.
- STOC-2015-LeeRS #bound #programming
- Lower Bounds on the Size of Semidefinite Programming Relaxations (JRL, PR, DS), pp. 567–576.
- STOC-2015-MekaPW #bound #clique
- Sum-of-squares Lower Bounds for Planted Clique (RM, AP, AW), pp. 87–96.
- ICALP-v1-2015-Ailon #bound #fourier
- Tighter Fourier Transform Lower Bounds (NA), pp. 14–25.
- ICALP-v1-2015-FominGKM #bound #graph #morphism #problem
- Lower Bounds for the Graph Homomorphism Problem (FVF, AG, ASK, IM), pp. 481–493.
- ICALP-v1-2015-KayalKPS #bound
- Lower Bounds for Sums of Powers of Low Degree Univariates (NK, PK, TP, CS), pp. 810–821.
- LATA-2015-AmanoS #bound #multi #polynomial
- A Nonuniform Circuit Class with Multilayer of Threshold Gates Having Super Quasi Polynomial Size Lower Bounds Against NEXP (KA, AS), pp. 461–472.
- ICML-2015-AgarwalB #bound #finite #optimisation
- A Lower Bound for the Optimization of Finite Sums (AA, LB), pp. 78–86.
- ICML-2015-ZhangWJ #algorithm #bound #distributed #estimation #matrix #performance #rank
- Distributed Estimation of Generalized Matrix Rank: Efficient Algorithms and Lower Bounds (YZ, MJW, MIJ), pp. 457–465.
- ICML-2015-ZhuG #complexity #robust #towards
- Towards a Lower Sample Complexity for Robust One-bit Compressed Sensing (RZ, QG), pp. 739–747.
- SIGIR-2015-Shen
- Lower Search Cost (DS), p. 1087.
- SAC-2015-OliveiraQMM #community #complexity #detection #using
- Community detection, with lower time complexity, using coupled Kuramoto oscillators (JEMdO, MGQ, MDNM, EENM), pp. 1160–1166.
- CADE-2015-GorznyP #first-order #proving #towards
- Towards the Compression of First-Order Resolution Proofs by Lowering Unit Clauses (JG, BWP), pp. 356–366.
- LICS-2015-KrebsV #bound #logic #refinement
- Universal Covers, Color Refinement, and Two-Variable Counting Logic: Lower Bounds for the Depth (AK, OV), pp. 689–700.
- RTA-2015-FrohnGHAS #bound #complexity #runtime
- Inferring Lower Bounds for Runtime Complexity (FF, JG, JH, CA, TS), pp. 334–349.
- CASE-2014-JacksonELMPCC #development
- Development of an active powered biped lower limb exoskeleton (SJ, LE, CL, PM, KP, MC, XC), pp. 990–995.
- ITiCSE-2014-MI #bound #query
- A method to prove query lower bounds (JM, SI), pp. 81–86.
- STOC-2014-FournierLMS #bound #matrix #multi
- Lower bounds for depth 4 formulas computing iterated matrix multiplication (HF, NL, GM, SS), pp. 128–135.
- STOC-2014-GavinskyMWW #approach #bound #complexity #composition #towards
- Toward better formula lower bounds: an information complexity approach to the KRW composition conjecture (DG, OM, OW, AW), pp. 213–222.
- STOC-2014-GoosP #bound #communication
- Communication lower bounds via critical block sensitivity (MG, TP), pp. 847–856.
- STOC-2014-KayalLSS #bound
- Super-polynomial lower bounds for depth-4 homogeneous arithmetic formulas (NK, NL, CS, SS), pp. 119–127.
- STOC-2014-KayalSS #bound
- A super-polynomial lower bound for regular arithmetic formulas (NK, CS, RS), pp. 146–153.
- STOC-2014-Williams #algorithm #bound #linear
- New algorithms and lower bounds for circuits with linear threshold gates (RW), pp. 194–202.
- ICALP-v1-2014-BrietDHS #approximate #bound
- Lower Bounds for Approximate LDCs (JB, ZD, GH, SS), pp. 259–270.
- ICALP-v1-2014-KumarS #bound
- Superpolynomial Lower Bounds for General Homogeneous Depth 4 Arithmetic Circuits (MK, SS), pp. 751–762.
- ICALP-v1-2014-NelsonN #bound
- Lower Bounds for Oblivious Subspace Embeddings (JN, HLN), pp. 883–894.
- ICALP-v1-2014-Volkovich #bound #learning #on the
- On Learning, Lower Bounds and (un)Keeping Promises (IV), pp. 1027–1038.
- CHI-2014-BohmerLGBK #design #smarttech
- Interrupted by a phone call: exploring designs for lowering the impact of call notifications for smartphone users (MB, CL, SG, DPB, AK), pp. 3045–3054.
- DHM-2014-FuCLCZ #framework #modelling
- Evaluating Work Disability of Lower Limb Handicapped within a Human Modeling Framework (YF, XC, SL, JGC, BZ), pp. 516–526.
- ICML-c1-2014-CombesP #algorithm #bound
- Unimodal Bandits: Regret Lower Bounds and Optimal Algorithms (RC, AP), pp. 521–529.
- ICML-c2-2014-MuHWG #bound
- Square Deal: Lower Bounds and Improved Relaxations for Tensor Recovery (CM, BH, JW, DG), pp. 73–81.
- ICML-c2-2014-ToshD #bound
- Lower Bounds for the Gibbs Sampler over Mixtures of Gaussians (CT, SD), pp. 1467–1475.
- ICPR-2014-IslamCK #case study #forensics #geometry
- A Preliminary Study of Lower Leg Geometry as a Soft Biometric Trait for Forensic Investigation (MRI, FKSC, AWKK), pp. 427–431.
- SAT-2014-JarvisaloK #bound
- Conditional Lower Bounds for Failed Literals and Related Techniques (MJ, JHK), pp. 75–84.
- CASE-2013-ChenZL #approach #design #novel
- A novel design approach for lower limb rehabilitation training robot (JC, XZ, RL), pp. 554–557.
- VLDB-2013-AfratiSSU #bound #cost analysis
- Upper and Lower Bounds on the Cost of a Map-Reduce Computation (FNA, ADS, SS, JDU), pp. 277–288.
- STOC-2013-Ajtai #bound #quantifier
- Lower bounds for RAMs and quantifier elimination (MA), pp. 803–812.
- STOC-2013-BurgisserI #bound #complexity #geometry
- Explicit lower bounds via geometric complexity theory (PB, CI), pp. 141–150.
- STOC-2013-FeldmanGRVX #algorithm #bound #clique #detection #statistics
- Statistical algorithms and a lower bound for detecting planted cliques (VF, EG, LR, SV, YX), pp. 655–664.
- STOC-2013-KomargodskiR #bound
- Average-case lower bounds for formula size (IK, RR), pp. 171–180.
- STOC-2013-NelsonN #bound
- Sparsity lower bounds for dimensionality reducing maps (JN, HLN), pp. 101–110.
- STOC-2013-Sherstov #bound #communication #using
- Communication lower bounds using directional derivatives (AAS), pp. 921–930.
- ICALP-v1-2013-AndoniNPW #bound #linear #sketching
- Tight Lower Bound for Linear Sketches of Moments (AA, HLN, YP, YW), pp. 25–32.
- ICALP-v1-2013-BunT #approximate #bound
- Dual Lower Bounds for Approximate Degree and Markov-Bernstein Inequalities (MB, JT), pp. 303–314.
- ICALP-v1-2013-FilmusLMNV #bound #calculus #comprehension #polynomial #towards
- Towards an Understanding of Polynomial Calculus: New Separations and Lower Bounds — (Extended Abstract) (YF, ML, MM, JN, MV), pp. 437–448.
- ICALP-v1-2013-KumarMN #bound
- Arithmetic Circuit Lower Bounds via MaxRank (MK, GM, JS), pp. 661–672.
- ICALP-v1-2013-Lampis #bound #graph #model checking
- Model Checking Lower Bounds for Simple Graphs (ML), pp. 673–683.
- ICALP-v1-2013-Leonardos #bound #complexity #random #recursion
- An Improved Lower Bound for the Randomized Decision Tree Complexity of Recursive Majority, (NL), pp. 696–708.
- LATA-2013-Tveretina #bound
- A Conditional Superpolynomial Lower Bound for Extended Resolution (OT), pp. 559–569.
- ESEC-FSE-2013-PetkeYCH #combinator #detection #fault #interactive #performance #testing
- Efficiency and early fault detection with lower and higher strength combinatorial interaction testing (JP, SY, MBC, MH), pp. 26–36.
- SAT-2013-Lauria #bound #proving #rank #theorem
- A Rank Lower Bound for Cutting Planes Proofs of Ramsey’s Theorem (ML), pp. 351–364.
- SAT-2013-MisraORS #bound #detection #set
- Upper and Lower Bounds for Weak Backdoor Set Detection (NM, SO, VR, SS), pp. 394–402.
- CASE-2012-HeZWZ #identification #using
- Identification of dynamic posture in lower extremity using optical fiber sensor (CH, XZ, YW, ZZ), pp. 1057–1060.
- STOC-2012-AgrawalSSS #bound
- Jacobian hits circuits: hitting-sets, lower bounds for depth-D occur-k formulas & depth-3 transcendence degree-k circuits (MA, CS, RS, NS), pp. 599–614.
- STOC-2012-BeameBI #bound #trade-off
- Time-space tradeoffs in resolution: superpolynomial lower bounds for superlinear space (PB, CB, RI), pp. 213–232.
- STOC-2012-BulanekKS #bound #online #problem
- Tight lower bounds for the online labeling problem (JB, MK, MES), pp. 1185–1198.
- STOC-2012-FioriniMPTW #bound #exponential #linear
- Linear vs. semidefinite extended formulations: exponential separation and strong lower bounds (SF, SM, SP, HRT, RdW), pp. 95–106.
- STOC-2012-GiakkoupisW #bound #random
- A tight RMR lower bound for randomized mutual exclusion (GG, PW), pp. 983–1002.
- ICALP-v1-2012-KapralovP #bound #metric
- NNS Lower Bounds via Metric Expansion for l ∞ and EMD (MK, RP), pp. 545–556.
- ICALP-v1-2012-Marx #bound #multi
- A Tight Lower Bound for Planar Multiway Cut with Fixed Number of Terminals (DM), pp. 677–688.
- ICALP-v2-2012-AtseriasD #approximate #bound #quantifier
- Degree Lower Bounds of Tower-Type for Approximating Formulas with Parity Quantifiers (AA, AD), pp. 67–78.
- ICALP-v2-2012-KikotKPZ #bound #exponential #query
- Exponential Lower Bounds and Separation for Query Rewriting (SK, RK, VVP, MZ), pp. 263–274.
- KDD-2012-OuyangG #adaptation #named #performance
- NASA: achieving lower regrets and faster rates via adaptive stepsizes (HO, AGG), pp. 159–167.
- SAC-2012-OliveiraCS #bound #on the #using
- On using adversary simulators to obtain tight lower bounds for response times (RSdO, AC, RAS), pp. 1573–1579.
- LICS-2012-Berkholz #bound #game studies #testing
- Lower Bounds for Existential Pebble Games and k-Consistency Tests (CB), pp. 25–34.
- SAT-2012-AchlioptasM #algorithm #bound #exponential #random #satisfiability
- Exponential Lower Bounds for DPLL Algorithms on Satisfiable Random 3-CNF Formulas (DA, RMM), pp. 327–340.
- CASE-2011-WuS #bound #multi #problem
- A lower and upper bound guided nested partitions method for solving capacitated multi-level production planning problems (TW, LS), pp. 78–83.
- DATE-2011-Wang #coordination #gpu #kernel #power management
- Coordinate strip-mining and kernel fusion to lower power consumption on GPU (GW), pp. 1218–1219.
- STOC-2011-ChakrabartiR #bound #communication #complexity
- An optimal lower bound on the communication complexity of gap-hamming-distance (AC, OR), pp. 51–60.
- STOC-2011-FriedmannHZ #algorithm #bound #random
- Subexponential lower bounds for randomized pivoting rules for the simplex algorithm (OF, TDH, UZ), pp. 283–292.
- ICALP-v1-2011-CliffordJ #bound #integer #multi #online
- Lower Bounds for Online Integer Multiplication and Convolution in the Cell-Probe Model (RC, MJ), pp. 593–604.
- ICALP-v1-2011-FilmusPS #bound #exponential
- Exponential Lower Bounds for AC0-Frege Imply Superpolynomial Frege Lower Bounds (YF, TP, RS), pp. 618–629.
- ICALP-v1-2011-HarkinsH #algorithm #bound #game studies #learning
- Exact Learning Algorithms, Betting Games, and Circuit Lower Bounds (RCH, JMH), pp. 416–423.
- ICALP-v1-2011-Zhang #bound #communication #complexity #on the #power of #quantum
- On the Power of Lower Bound Methods for One-Way Quantum Communication Complexity (SZ), pp. 49–60.
- CIKM-2011-LvZ #bound #normalisation
- Lower-bounding term frequency normalization (YL, CZ), pp. 7–16.
- ICML-2011-Gould #learning #linear #markov #random
- Max-margin Learning for Lower Linear Envelope Potentials in Binary Markov Random Fields (SG), pp. 193–200.
- LCTES-2011-ThomasFK #execution #monitoring
- Lowering overhead in sampling-based execution monitoring and tracing (JJT, SF, DK), pp. 101–110.
- SAT-2011-Williams #algorithm #bound #complexity #satisfiability
- Connecting SAT Algorithms and Complexity Lower Bounds (RW), pp. 1–2.
- STOC-2010-Patrascu #bound #polynomial #problem #towards
- Towards polynomial lower bounds for dynamic problems (MP), pp. 603–610.
- STOC-2010-Raz #bound
- Tensor-rank and lower bounds for arithmetic formulas (RR), pp. 659–666.
- STOC-2010-VerbinZ #bound #memory management
- The limits of buffering: a tight lower bound for dynamic membership in the external memory model (EV, QZ), pp. 447–456.
- STOC-2010-Williams #bound
- Improving exhaustive search implies superpolynomial lower bounds (RW), pp. 231–240.
- ICALP-v1-2010-GreveJLT #approximate #bound
- Cell Probe Lower Bounds and Approximations for Range Mode (MG, AGJ, KDL, JT), pp. 605–616.
- ICALP-v2-2010-Fearnley #bound #exponential #policy
- Exponential Lower Bounds for Policy Iteration (JF), pp. 551–562.
- LICS-2010-KreutzerT #bound #complexity #higher-order #logic #monad
- Lower Bounds for the Complexity of Monadic Second-Order Logic (SK, ST), pp. 189–198.
- SAT-2010-Ben-SassonJ #bound #learning #strict
- Lower Bounds for Width-Restricted Clause Learning on Small Width Formulas (EBS, JJ), pp. 16–29.
- PODS-2009-Yi #bound #query
- Dynamic indexability and lower bounds for dynamic one-dimensional range query indexes (KY), pp. 187–196.
- ITiCSE-2009-BrindaPS #education #standard
- Bridging ICT and CS: educational standards for computer science in lower secondary education (TB, HP, CS), pp. 288–292.
- FoSSaCS-2009-KupfermanP #automaton #bound
- Lower Bounds on Witnesses for Nonemptiness of Universal Co-Büchi Automata (OK, NP), pp. 182–196.
- STOC-2009-BateniCG #bound
- MaxMin allocation via degree lower-bounded arborescences (MB, MC, VG), pp. 543–552.
- STOC-2009-DietzfelbingerW #bound
- Tight lower bounds for greedy routing in uniform small world rings (MD, PW), pp. 591–600.
- STOC-2009-Viola #bound #data type
- Bit-probe lower bounds for succinct data structures (EV), pp. 475–482.
- ICALP-v1-2009-BuhrmanFS #bound
- Unconditional Lower Bounds against Advice (HB, LF, RS), pp. 195–209.
- ICALP-v1-2009-GuhaH #bound #order #random #theorem
- Revisiting the Direct Sum Theorem and Space Lower Bounds in Random Order Streams (SG, ZH), pp. 513–524.
- ICALP-v2-2009-ColcombetZ #automaton #bound
- A Tight Lower Bound for Determinization of Transition Labeled Büchi Automata (TC, KZ), pp. 151–162.
- LATA-2009-Bollig #bound #complexity #integer #multi
- Larger Lower Bounds on the OBDD Complexity of Integer Multiplication (BB), pp. 212–223.
- DHM-2009-FuLYB #predict
- Simulation-Based Discomfort Prediction of the Lower Limb Handicapped with Prosthesis in the Climbing Tasks (YF, SL, MY, YB), pp. 512–520.
- SAC-2009-ManuchSS #bound #self
- Two lower bounds for self-assemblies at temperature 1 (JM, LS, CS), pp. 808–809.
- LICS-2009-CaiZL #automaton #bound
- An Improved Lower Bound for the Complementation of Rabin Automata (YC, TZ, HL), pp. 167–176.
- LICS-2009-Friedmann #algorithm #bound #exponential #game studies
- An Exponential Lower Bound for the Parity Game Strategy Improvement Algorithm as We Know it (OF), pp. 145–156.
- SAT-2009-Johannsen #bound #exponential #learning #strict
- An Exponential Lower Bound for Width-Restricted Clause Learning (JJ), pp. 128–140.
- FoSSaCS-2008-GruberJ #bound #communication #complexity #regular expression #using
- Optimal Lower Bounds on Regular Expression Size Using Communication Complexity (HG, JJ), pp. 273–286.
- STOC-2008-AttiyaHW #bound #problem
- Tight rmr lower bounds for mutual exclusion and other problems (HA, DH, PW), pp. 217–226.
- STOC-2008-CaiCL #bound #exclamation #polynomial #problem
- A quadratic lower bound for the permanent and determinant problem over any characteristic != 2 (JyC, XC, DL), pp. 491–498.
- STOC-2008-ChakrabartiCM #bound #communication #robust
- Robust lower bounds for communication and stream computation (AC, GC, AM), pp. 641–650.
- STOC-2008-Raz #bound
- Elusive functions and lower bounds for arithmetic circuits (RR), pp. 711–720.
- STOC-2008-Sherstov #bound #communication #matrix #quantum
- The pattern matrix method for lower bounds on quantum communication (AAS), pp. 85–94.
- DLT-2008-HromkovicS #automaton #bound #nondeterminism #on the #proving
- On the Hardness of Determining Small NFA’s and of Proving Lower Bounds on Their Sizes (JH, GS), pp. 34–55.
- ICALP-A-2008-ChildsL #bound #order #quantum
- Optimal Quantum Adversary Lower Bounds for Ordered Search (AMC, TL), pp. 869–880.
- ICALP-A-2008-GuhaM #bound #multi
- Tight Lower Bounds for Multi-pass Stream Computation Via Pass Elimination (SG, AM), pp. 760–772.
- ICALP-A-2008-Saxena #bound #testing
- Diagonal Circuit Identity Testing and Lower Bounds (NS), pp. 60–71.
- LATA-2008-Mercer #automaton #bound #finite #quantum
- Lower Bounds for Generalized Quantum Finite Automata (MM), pp. 373–384.
- LICS-2008-Moschovakis #axiom #bound
- The Axiomatic Derivation of Absolute Lower Bounds (YNM), p. 405.
- PODS-2007-Schweikardt #bound #modelling #query
- Machine models and lower bounds for query processing (NS), pp. 41–52.
- FoSSaCS-2007-MuschollW #bound #composition #web #web service
- A Lower Bound on Web Services Composition (AM, IW), pp. 274–286.
- PEPM-2007-BurchettCK #functional #named #optimisation
- Lowering: a static optimization technique for transparent functional reactivity (KB, GHC, SK), pp. 71–80.
- STOC-2007-BeameJR #algorithm #bound #random
- Lower bounds for randomized read/write stream algorithms (PB, TSJ, AR), pp. 689–698.
- STOC-2007-LinialS #bound #communication #complexity
- Lower bounds in communication complexity based on factorization norms (NL, AS), pp. 699–708.
- STOC-2007-Patrascu #2d #bound
- Lower bounds for 2-dimensional range counting (MP), pp. 40–46.
- STOC-2007-Santhanam #bound
- Circuit lower bounds for Merlin-Arthur classes (RS), pp. 275–283.
- ICALP-2007-BozzelliT #automaton #bound #parametricity #problem
- Decision Problems for Lower/Upper Bound Parametric Timed Automata (LB, SLT), pp. 925–936.
- ICALP-2007-GuhaM #bound #estimation #multi #streaming
- Lower Bounds for Quantile Estimation in Random-Order and Multi-pass Streaming (SG, AM), pp. 704–715.
- ICALP-2007-MontanaroW #bound #communication #complexity #quantum
- A Lower Bound on Entanglement-Assisted Quantum Communication Complexity (AM, AJW), pp. 122–133.
- DHM-2007-YangWZJW #analysis
- Redundant Muscular Force Analysis of Human Lower Limbs During Rising from a Squat (YY, RW, MZ, DJ, FW), pp. 259–267.
- SAC-2007-GilPFM #embedded
- Embedded system for diagnosing dysfunctions in the lower urinary tract (DGM, ASP, DRF, CAM), pp. 1695–1699.
- SAT-2007-Kojevnikov #bound #linear
- Improved Lower Bounds for Tree-Like Resolution over Linear Inequalities (AK), pp. 70–79.
- PODS-2006-GroheHS #bound #random #scalability #set
- Randomized computations on large data sets: tight lower bounds (MG, AH, NS), pp. 243–252.
- STOC-2006-AmbainisSW #bound #quantum #theorem #trade-off
- A new quantum lower bound method, : with applications to direct product theorems and time-space tradeoffs (AA, RS, RdW), pp. 618–633.
- STOC-2006-Zhang #bound #quantum #random
- New upper and lower bounds for randomized and quantum local search (SZ), pp. 634–643.
- DLT-2006-BellP #bound #matrix
- Lowering Undecidability Bounds for Decision Questions in Matrices (PB, IP), pp. 375–385.
- DLT-2006-GruberH #bound #complexity #nondeterminism
- Finding Lower Bounds for Nondeterministic State Complexity Is Hard (HG, MH), pp. 363–374.
- ICALP-v1-2006-Golynski #bound #rank
- Optimal Lower Bounds for Rank and Select Indexes (AG), pp. 370–381.
- ICALP-v1-2006-KojevnikovI #bound #calculus #proving
- Lower Bounds of Static Lovász-Schrijver Calculus Proofs for Tseitin Tautologies (AK, DI), pp. 323–334.
- ICALP-v1-2006-Wolf #bound #matrix #quantum
- Lower Bounds on Matrix Rigidity Via a Quantum Argument (RdW), pp. 62–71.
- ICALP-v2-2006-Yan #automaton #bound
- Lower Bounds for Complementation of ω-Automata Via the Full Automata Technique (QY), pp. 589–600.
- LICS-2006-MacielP #bound #composition #proving
- Conditional Lower Bound for a System of Constant-Depth Proofs with Modular Connectives (AM, TP), pp. 189–200.
- DATE-2005-ManquinhoM #bound #effectiveness #optimisation #pseudo
- Effective Lower Bounding Techniques for Pseudo-Boolean Optimization (VMM, JPMS), pp. 660–665.
- PODS-2005-GroheS #bound #memory management #random #sorting
- Lower bounds for sorting with few random accesses to external memory (MG, NS), pp. 238–249.
- ITiCSE-2005-Hamza #analysis #approach #design #object-oriented
- Introducing object-oriented analysis and design in lower-level undergraduate courses: a pattern-based approach (HSH), p. 350.
- STOC-2005-Alekhnovich #bound #random
- Lower bounds for k-DNF resolution on random 3-CNFs (MA), pp. 251–256.
- STOC-2005-ElkinEST
- Lower-stretch spanning trees (ME, YE, DAS, SHT), pp. 494–503.
- STOC-2005-GafniGP #adaptation #bound #complexity #set
- From a static impossibility to an adaptive lower bound: the complexity of early deciding set agreement (EG, RG, BP), pp. 714–722.
- ICALP-2005-BeamePS #bound #communication #complexity #multi
- Lower Bounds for Lovász-Schrijver Systems and Beyond Follow from Multiparty Communication Complexity (PB, TP, NS), pp. 1176–1188.
- ICALP-2005-ChattopadhyayH #bound #composition #symmetry
- Lower Bounds for Circuits with Few Modular and Symmetric Gates (AC, KAH), pp. 994–1005.
- ICALP-2005-DiehlM #bound #polynomial #random
- Time-Space Lower Bounds for the Polynomial-Time Hierarchy on Randomized Machines (SD, DvM), pp. 982–993.
- ICALP-2005-FordG #bound #communication #complexity #multi
- Hadamard Tensors and Lower Bounds on Multiparty Communication Complexity (JF, AG), pp. 1163–1175.
- ICALP-2005-GroheKS #bound #memory management #query #streaming
- Tight Lower Bounds for Query Processing on Streaming and External Memory Data (MG, CK, NS), pp. 1076–1088.
- ICALP-2005-KoiranNP #bound #complexity #problem #quantum #query
- A Quantum Lower Bound for the Query Complexity of Simon’s Problem (PK, VN, NP), pp. 1287–1298.
- ICALP-2005-WehnerW #bound #information retrieval
- Improved Lower Bounds for Locally Decodable Codes and Private Information Retrieval (SW, RdW), pp. 1424–1436.
- SAT-2005-Gelder #bound #distance #proving
- Input Distance and Lower Bounds for Propositional Resolution Proof Length (AVG), pp. 282–293.
- SAT-2005-HeuleM #bound #linear #programming #random #satisfiability #using
- Observed Lower Bounds for Random 3-SAT Phase Transition Density Using Linear Programming (MH, HvM), pp. 122–134.
- FoSSaCS-2004-LuttgenV #bisimulation #bound
- Bisimulation on Speed: Lower Time Bounds (GL, WV), pp. 333–347.
- TACAS-2004-BehrmannBLP #abstraction #automaton #bound
- Lower and Upper Bounds in Zone Based Abstractions of Timed Automata (GB, PB, KGL, RP), pp. 312–326.
- STOC-2004-Aaronson04a #bound #quantum
- Lower bounds for local search by quantum arguments (SA), pp. 465–474.
- STOC-2004-AilonC #bound #linear #testing
- Lower bounds for linear degeneracy testing (NA, BC), pp. 554–560.
- STOC-2004-ChenHKX #bound #linear #reduction
- Linear FPT reductions and computational lower bounds (JC, XH, IAK, GX), pp. 212–221.
- STOC-2004-Elkin #approximate #bound #distributed #problem #trade-off
- Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem (ME), pp. 331–340.
- STOC-2004-PatrascuD #bound
- Lower bounds for dynamic connectivity (MP, EDD), pp. 546–553.
- ICALP-2004-AlekhnovichHI #algorithm #bound #exponential #satisfiability
- Exponential Lower Bounds for the Running Time of DPLL Algorithms on Satisfiable Formulas (MA, EAH, DI), pp. 84–96.
- ICALP-2004-MelkebeekR #bound #satisfiability
- A Time Lower Bound for Satisfiability (DvM, RR), pp. 971–982.
- ICALP-2004-Midrijanis #bound #polynomial #problem #quantum #query #set #similarity
- A Polynomial Quantum Query Lower Bound for the Set Equality Problem (GM), pp. 996–1005.
- ICALP-2004-Zhang #bound #on the #power of
- On the Power of Ambainis’s Lower Bounds (SZ), pp. 1238–1250.
- CHI-2004-PoFB #visual notation
- Mouse and touchscreen selection in the upper and lower visual fields (BAP, BDF, KSB), pp. 359–366.
- ICML-2004-ConitzerS #bound #communication #complexity #game studies #learning
- Communication complexity as a lower bound for learning in games (VC, TS).
- CGO-2004-JoshiBZ #optimisation #profiling #staged
- Targeted Path Profiling: Lower Overhead Path Profiling for Staged Dynamic Optimization Systems (RJ, MDB, CBZ), pp. 239–250.
- SAT-2004-ManquinhoM #bound #optimisation #pseudo #satisfiability #using
- Using Lower-Bound Estimates in SAT-Based Pseudo-Boolean Optimization (VMM, JPMS), pp. 120–126.
- DATE-2003-EbendtGD #bound
- Combination of Lower Bounds in Exact BDD Minimization (RE, WG, RD), pp. 10758–10763.
- STOC-2003-Bar-Yossef #bound
- Sampling lower bounds via information theory (ZBY), pp. 335–344.
- STOC-2003-FatourouFR #bound #implementation #multi
- A tight time lower bound for space-optimal implementations of multi-writer snapshots (PF, FEF, ER), pp. 259–268.
- STOC-2003-GalR #bound
- Lower bounds on the amount of randomness in private computation (AG, AR), pp. 659–666.
- STOC-2003-GennaroGK #bound #encryption #performance
- Lower bounds on the efficiency of encryption and digital signature schemes (RG, YG, JK), pp. 417–425.
- STOC-2003-JayramKKR #bound #problem
- Cell-probe lower bounds for the partial match problem (TSJ, SK, RK, YR), pp. 667–672.
- STOC-2003-KabanetsI #bound #polynomial #proving #testing
- Derandomizing polynomial identity tests means proving circuit lower bounds (VK, RI), pp. 355–364.
- STOC-2003-KerenidisW #bound #exponential #quantum
- Exponential lower bound for 2-query locally decodable codes via a quantum argument (IK, RdW), pp. 106–115.
- STOC-2003-SauerhoffW #bound #graph #integer #multi #trade-off
- Time-space tradeoff lower bounds for integer multiplication and graphs of arithmetic functions (MS, PW), pp. 186–195.
- ICALP-2003-AmirACLP #algorithm #bound
- Function Matching: Algorithms, Applications, and a Lower Bound (AA, YA, RC, ML, EP), pp. 929–942.
- PODS-2002-Chirkova #bound #problem #query
- The View-Selection Problem Has an Exponential-Time Lower Bound for Conjunctive Queries and Views (RC), pp. 159–168.
- FoSSaCS-2002-JancarKMS #automaton #bound #proving
- Equivalence-Checking with One-Counter Automata: A Generic Method for Proving Lower Bounds (PJ, AK, FM, ZS), pp. 172–186.
- STOC-2002-Aaronson #bound #problem #quantum
- Quantum lower bound for the collision problem (SA), pp. 635–642.
- STOC-2002-Kontogiannis #algorithm #bound #online #scheduling
- Lower bounds & competitive algorithms for online scheduling of unit-size tasks to related machines (SCK), pp. 124–133.
- STOC-2002-Raz02a #bound #principle
- Resolution lower bounds for the weak pigeonhole principle (RR), pp. 553–562.
- STOC-2002-SaksS #approximate #bound #data type #distance
- Space lower bounds for distance approximation in the data stream model (MES, XS), pp. 360–369.
- DLT-2002-SasakiIIW #2d #bound #probability #turing machine
- A Space Lower Bound of Two-Dimensional Probabilistic Turing Machines (YS, KI, AI, YW), pp. 185–196.
- ICALP-2002-GrigorievHP #algebra #bound #exponential #proving
- Exponential Lower Bound for Static Semi-algebraic Proofs (DG, EAH, DVP), pp. 257–268.
- SEKE-2002-WohlinA #order
- Analysing primary and lower order project success drivers (CW, AAA), pp. 393–400.
- STOC-2001-Ambainis #bound #protocol #quantum
- A new protocol and lower bounds for quantum coin flipping (AA), pp. 134–142.
- STOC-2001-Bar-YossefKS #algorithm #bound
- Sampling algorithms: lower bounds and applications (ZBY, RK, DS), pp. 266–275.
- STOC-2001-BolligW #bound #branch #integer #multi #using
- A read-once branching program lower bound of Ω(2n/4) for integer multiplication using universal (BB, PW), pp. 419–424.
- STOC-2001-ChazelleL #bound
- Lower bounds for intersection searching and fractional cascading in higher dimension (BC, DL), pp. 322–329.
- STOC-2001-LachishR #bound
- Explicit lower bound of 4.5n — o(n) for boolena circuits (OL, RR), pp. 399–408.
- STOC-2001-PitassiR #bound #principle
- Regular resolution lower bounds for the weak pigeonhole principle (TP, RR), pp. 347–355.
- STOC-2001-RazS #bound #matrix
- Lower bounds for matrix product, in bounded depth circuits with arbitrary gates (RR, AS), pp. 409–418.
- ICALP-2001-AtseriasBE #bound
- Lower Bounds for the Weak Pigeonhole Principle Beyond Resolution (AA, MLB, JLE), pp. 1005–1016.
- ICALP-2001-ChakrabartiK #bound #complexity #graph #random
- Improved Lower Bounds on the Randomized Complexity of Graph Properties (AC, SK), pp. 285–296.
- ICALP-2001-SenV #bound #quantum
- Lower Bounds in the Quantum Cell Probe Model (PS, SV), pp. 358–369.
- LICS-2001-AdlerI #bound #exclamation
- An n! Lower Bound on Formula Size (MA, NI), pp. 197–206.
- DAC-2000-NarasimhanR #bound #on the #problem #scheduling #synthesis
- On lower bounds for scheduling problems in high-level synthesis (MN, JR), pp. 546–551.
- DATE-2000-KruseSJSN #bound #constraints #data flow #graph #power management
- Lower Bounds on the Power Consumption in Scheduled Data Flow Graphs with Resource Constraints (LK, ES, GJ, AS, WN), p. 737.
- CSMR-2000-BrilFGKW #algebra #multi #using
- Hiding Expressed Using Relation Algebra with Multi-Relations — Oblique Lifting and Lowering for Unbalanced Systems (RJB, LMGF, AG, RLK, TW), pp. 33–44.
- IWPC-2000-AntoniolCM #identification
- Identification of Lower-Level Artifacts (GA, GC, EM), p. 253.
- STOC-2000-Achlioptas #bound #random #satisfiability
- Setting 2 variables at a time yields a new lower bound for random 3-SAT (extended abstract) (DA), pp. 28–37.
- STOC-2000-Ambainis #bound #quantum
- Quantum lower bounds by quantum arguments (AA), pp. 636–643.
- STOC-2000-HarnikR #bound
- Higher lower bounds on monotone size (DH, RR), pp. 378–387.
- ICALP-2000-FournierK #bound
- Lower Bounds Are Not Easier over the Reals: Inside PH (HF, PK), pp. 832–843.
- ICPR-v4-2000-BarataPG #image
- Segmenting at Higher Scales to Classify at Lower Scales. A Mathematical Morphology Based Methodology Applied to Forest Cover Remote Sensing Images (TB, PP, IG), pp. 4084–4087.
- DAC-1999-DrechslerG #bound #using
- Using Lower Bounds During Dynamic BDD Minimization (RD, WG), pp. 29–32.
- DAC-1999-HemaniMKPONOEL #design #power management #using
- Lowering Power Consumption in Clock by Using Globally Asynchronous Locally Synchronous Design Style (AH, TM, SK, AP, TO, PN, JÖ, PE, DL), pp. 873–878.
- STOC-1999-AmbainisNTV #automaton #bound #quantum
- Dense Quantum Coding and a Lower Bound for 1-Way Quantum Automata (AA, AN, ATS, UVV), pp. 376–383.
- STOC-1999-BorodinOR #bound #nearest neighbour #problem
- Lower Bounds for High Dimensional Nearest Neighbor Search and Related Problems (AB, RO, YR), pp. 312–321.
- STOC-1999-ChakrabartiCGL #approximate #bound #complexity #nearest neighbour
- A Lower Bound on the Complexity of Approximate Nearest-Neighbor Searching on the Hamming Cube (AC, BC, BG, AL), pp. 305–311.
- STOC-1999-RussellSZ #bound
- Lower Bounds for Leader Election and Collective Coin-Flipping in the Perfect Information Model (AR, MES, DZ), pp. 339–347.
- ICALP-1999-AndreevBCR #bound #branch #pseudo #set #source code
- Small Pseudo-Random Sets Yield Hard Functions: New Tight Explict Lower Bounds for Branching Programs (AEA, JLB, AEFC, JDPR), pp. 179–189.
- CSL-1999-Toran #bound
- Lower Bounds for Space in Resolution (JT), pp. 362–373.
- LICS-1999-Libkin #bound #invariant #logic #query
- Logics with Counting, Auxiliary Relations, and Lower Bounds for Invariant Queries (LL), pp. 316–325.
- PODS-1998-SamoladasM #bound #multi #query #theorem
- A Lower Bound Theorem for Indexing Schemes and Its Application to Multidimensional Range Queries (VS, DPM), pp. 44–51.
- STOC-1998-FournierK #bound #question
- Are Lower Bounds Easier over the Reals? (HF, PK), pp. 507–513.
- STOC-1998-Gal #bound #source code
- A Characterization of Span Program Size and Improved Lower Bounds for Monotone Span Programs (AG), pp. 429–437.
- STOC-1998-Grigoriev #bound #complexity #random
- Randomized Complexity Lower Bounds (DG), pp. 219–223.
- STOC-1998-GrigorievK #bound #exponential
- An Exponential Lower Bound for Depth 3 Arithmetic Circuits (DG, MK), pp. 577–582.
- ICPR-1998-ArcelliS #parallel
- Parallel lowering of digital pictures by topology preserving operations (CA, LS), pp. 1601–1603.
- CSL-1998-Schwentick #bound #complexity #linear
- Descriptive Complexity, Lower Bounds and Linear Time (TS), pp. 9–28.
- DAC-1997-LiaoD #bound #problem #using
- Solving Covering Problems Using LPR-Based Lower Bounds (SYL, SD), pp. 117–120.
- ITiCSE-1997-FeldmanB #concurrent #education #programming
- Concurrent programming CAN be introduced into the lower-level undergraduate curriculum (MBF, BDB), pp. 77–79.
- STOC-1997-Aspnes #bound #distributed #random
- Lower Bounds for Distributed Coin-Flipping and Randomized Consensus (JA), pp. 559–568.
- STOC-1997-GrigorievK #bound #random
- Randomized Ω(n²) Lower Bound for Knapsack (DG, MK), pp. 76–85.
- STOC-1997-PaturiSZ #bound #exponential
- Exponential Lower Bounds for Depth 3 Boolean Circuits (RP, MES, FZ), pp. 86–91.
- DLT-1997-KarhumakiPM #bound #constant
- A lower bound for a constant in Shallit’s conjecture (JK, WP, FM), pp. 103–118.
- HCI-CC-1997-Komatsubara
- Psychological Upper and Lower Limits of System Response Time and User’s Preference on Skill Level (AK), pp. 829–832.
- TRI-Ada-1997-Gonzalez-BarahonaCQBL #ada #education #network #programming
- Teaching Network Programming with Ada and Lower_Layer (JMGB, JCG, PdlHQ, FJBC, LLF), pp. 105–110.
- CSL-1997-BonetG #bound #linear #simulation
- Linear Lower Bounds and Simulations in Frege Systems with Substitutions (MLB, NG), pp. 115–128.
- ILPS-1997-DebrayLHL #bound #estimation #logic programming #source code
- Lower Bound Cost Estimation for Logic Programs (SKD, PLG, MVH, NWL), pp. 291–305.
- ILPS-1997-KingSB #analysis #bound #logic programming #source code
- Lower-bound Time-complexity Analysis of Logic Programs (AK, KS, FB), pp. 261–275.
- DAC-1996-OhPP #bound #linear #programming #using
- Constructing Lower and Upper Bounded Delay Routing Trees Using Linear Programming (JO, IP, MP), pp. 401–404.
- DAC-1996-ParulkarGB #bound #data flow #graph
- Lower Bounds on Test Resources for Scheduled Data Flow Graphs (IP, SKG, MAB), pp. 143–148.
- STOC-1996-BabaiGKRSW #bound #graph #source code
- Extremal Bipartite Graphs and Superpolynomial Lower Bounds for Monotone Span Programs (LB, AG, JK, LR, TS, AW), pp. 603–611.
- STOC-1996-BartalFL #bound #graph #online #problem
- Lower Bounds for On-line Graph Problems with Application to On-line Circuit and Optical Routing (YB, AF, SL), pp. 531–540.
- STOC-1996-EvansP #bound
- Lower Bounds for Noisy Boolean Decision Trees (WSE, NP), pp. 620–628.
- STOC-1996-GrigorievKHS #algebra #bound #random
- A Lower Bound for Randomized Algebraic Decision Trees (DG, MK, FMadH, RS), pp. 612–619.
- ICALP-1996-BradfordR #bound
- Lower Bounds for Row Minima Searching (Extended Abstract) (PGB, KR), pp. 454–465.
- ICALP-1996-Miltersen #bound #multi
- Lower Bounds for Static Dictionaries on RAMs with Bit Operations But No Multiplication (PBM), pp. 442–453.
- ICALP-1996-Razborov #bound #independence #proving
- Lower Bounds for Propositional Proofs and Independence Results in Bounded Arithmetic (AAR), pp. 48–62.
- ICPR-1996-NewmanTBC #image #segmentation
- A volumetric segmentation technique for diagnosis and surgical planning in lower torso CT images (TSN, NT, SLB, PLC), pp. 553–557.
- CADE-1996-Vorobyov #bound
- An Improved Lower Bound for the Elementary Theories of Trees (SGV), pp. 275–287.
- STOC-1995-AnderssonHP #array #bound
- A tight lower bound for searching a sorted array (AA, JH, OP), pp. 417–426.
- STOC-1995-BonetPR #bound #proving
- Lower bounds for cutting planes proofs with small coefficients (MLB, TP, RR), pp. 575–584.
- STOC-1995-Chazelle #bound
- Lower bounds for off-line range searching (BC), pp. 733–740.
- STOC-1995-EdmondsP #bound
- A nearly optimal time-space lower bound for directed st-connectivity on the NNJAG model (JE, CKP), pp. 147–156.
- STOC-1995-Eppstein #bound #geometry #optimisation #parametricity
- Geometric lower bounds for parametric matroid optimization (DE), pp. 662–671.
- STOC-1995-KahaleLMPSS #bound #network #sorting
- Lower bounds for sorting networks (NK, FTL, YM, CGP, TS, ES), pp. 437–446.
- STOC-1995-Ponzio #bound #branch #integer #multi #source code
- A lower bound for integer multiplication with read-once branching programs (SP), pp. 130–139.
- ICALP-1995-Ben-AmramG #algebra #bound #random
- Lower Bounds on Algebraic Random Access Machines (Extended Abstract) (AMBA, ZG), pp. 360–371.
- ICALP-1995-FreivaldsK #bound #random
- Lower Time Bounds for Randomized Computation (RF, MK), pp. 183–195.
- POPL-1995-HoangM #bound #type inference #type system
- Lower Bounds on Type Inference with Subtypes (MH, JCM), pp. 176–185.
- EDAC-1994-DalkilicP #bound #scheduling #using
- Optimal Operation Scheduling Using Resource Lower Bound Estimations (MED, VP), pp. 319–324.
- STOC-1994-GrigorievKV #algebra #bound #testing
- Lower bounds on testing membership to a polyhedron by algebraic decision trees (DG, MK, NV), pp. 635–644.
- STOC-1994-Miltersen #bound #problem #random
- Lower bounds for union-split-find related problems on random access machines (PBM), pp. 625–634.
- STOC-1994-Mulmuley #bound #linear #parallel #problem #programming
- Lower bounds for parallel linear programming and other problems (KM), pp. 603–614.
- ICALP-1994-Bonizzoni #bound
- A Tight Lower Bound for Primitivity in k-Structures (PB), pp. 556–567.
- ICALP-1994-FreivaldsK #bound #random
- Lower Space Bounds for Randomized Computation (RF, MK), pp. 580–592.
- ICALP-1994-PlaxtonS #bound #network #sorting
- A Super-Logarithmic Lower Bound for Hypercubic Sorting Networks (CGP, TS), pp. 618–629.
- LICS-1994-ImpagliazzoPU #bound #proving
- Upper and Lower Bounds for Tree-Like Cutting Planes Proofs (RI, TP, AU), pp. 220–228.
- DAC-1993-TiwariAM
- Technology Mapping for Lower Power (VT, PA, SM), pp. 74–79.
- STOC-1993-KushilevitzMRZ #bound #random
- Lower bounds for randomized mutual exclusion (EK, YM, MOR, DZ), pp. 154–163.
- ICALP-1993-Ablayev #bound #communication #complexity #probability
- Lower Bounds for One-way Probabilistic Communication Complexity (FMA), pp. 241–252.
- TLCA-1993-Springintveld #bound #reduction
- Lower and Upper Bounds for Reductions of Types in λω and λP (JS), pp. 391–405.
- STOC-1992-BeameIKPPW #bound #exponential #principle
- Exponential Lower Bounds for the Pigeonhole Principle (PB, RI, JK, TP, PP, ARW), pp. 200–220.
- ICALP-1992-ChazelleR #bound #complexity #pointer
- Lower Bounds on the Complexity of Simplex Range Reporting on a Pointer Machine (BC, BR), pp. 439–449.
- STOC-1991-BreslauerG #bound #parallel #string
- A Lower Bound for Parallel String Matching (DB, ZG), pp. 439–443.
- STOC-1991-KarloffRR #algorithm #bound #random
- Lower Bounds for Randomized k-Server and Motion Planning Algorithms (HJK, YR, YR), pp. 278–288.
- STOC-1991-Nisan #bound #commutative
- Lower Bounds for Non-Commutative Computation (Extended Abstract) (NN), pp. 410–418.
- RTA-1991-Baader #bound #problem #unification
- Unification, Weak Unification, Upper Bound, Lower Bound, and Generalization Problems (FB), pp. 86–97.
- STOC-1990-Poutre #bound #pointer #problem
- Lower Bounds for the Union-Find and the Split-Find Problem on Pointer Machines (JALP), pp. 34–44.
- STOC-1990-Zuckerman #bound
- A Technique for Lower Bounding the Cover Time (DZ), pp. 254–259.
- CSL-1990-Ranaivoson #bound #graph #problem
- Nontrivial Lower Bounds for some NP-Problems on Directed Graphs (SR), pp. 318–339.
- STOC-1989-BorodinRT #bound #sequence #traversal
- Lower Bounds on the Length of Universal Traversal Sequences (Detailed Abstract) (AB, WLR, MT), pp. 562–573.
- ICALP-1989-AllenderH #bound
- Lower Bounds for the Low Hierarchy (Extended Abstract) (EA, LAH), pp. 31–45.
- ICALP-1989-BilardiM #bound
- Time Lower Bounds For CREW-PRAM Computation Of Monotone Functions (GB, AM), pp. 95–107.
- ICALP-1989-MansourST #bound
- Lower Bounds for Computations with the Floor Operation (YM, BS, PT), pp. 559–573.
- STOC-1988-King #bound #complexity #graph
- Lower Bounds on the Complexity of Graph Properties (VK), pp. 468–476.
- STOC-1987-Smolensky #algebra #bound #complexity #formal method
- Algebraic Methods in the Theory of Lower Bounds for Boolean Circuit Complexity (RS), pp. 77–82.
- ICALP-1987-Dietzfelbinger #bound #sorting
- Lower Bounds for Sorting of Sums (MD), pp. 457–466.
- ICALP-1987-MehlhornNA #bound #complexity #problem
- A Lower Bound for the Complexity of the Union-Split-Find Problem (KM, SN, HA), pp. 479–488.
- STOC-1986-AjtaiBHKPRST #bound #branch #source code
- Two lower bounds for branching programs (MA, LB, PH, JK, PP, VR, ES, GT), pp. 30–38.
- STOC-1986-Hastad #bound
- Almost Optimal Lower Bounds for Small Depth Circuits (JH), pp. 6–20.
- STOC-1986-LiY #bound #parallel
- New Lower Bounds for Parallel Computation (ML, YY), pp. 177–187.
- ICALP-1986-Schoning #bound #recursion
- Lower Bounds by Recursion Theoretic Arguments (Extended Abstract) (US), pp. 370–375.
- ICALP-1986-Willard #bound #problem #query
- Lower Bounds for Dynamic Range Query Problems That Permit Subtraction (Extended Abstract) (DEW), pp. 444–453.
- STOC-1985-FichHRW #bound #infinity #parallel
- One, Two, Three … Infinity: Lower Bounds for Parallel Computation (FEF, FMadH, PR, AW), pp. 48–58.
- STOC-1985-VardiS #bound #logic #source code
- Improved Upper and Lower Bounds for Modal Logics of Programs: Preliminary Report (MYV, LJS), pp. 240–251.
- ICALP-1985-Li #bound
- Lower Bounds by Kolmogorov-Complexity (Extended Abstract) (ML0), pp. 383–393.
- STOC-1984-DurisGS #bound #communication #complexity
- Lower Bounds on Communication Complexity (PD, ZG, GS), pp. 81–91.
- STOC-1984-Maass #bound #nondeterminism #polynomial #turing machine
- Quadratic Lower Bounds for Deterministic and Nondeterministic One-Tape Turing Machines (Extended Abstract) (WM), pp. 401–408.
- STOC-1983-Ben-Or #algebra #bound
- Lower Bounds for Algebraic Computation Trees (Preliminary Report) (MBO), pp. 80–86.
- STOC-1983-DurisGPR #bound
- Two Nonlinear Lower Bounds (PD, ZG, WJP, RR), pp. 127–132.
- STOC-1983-Valiant #bound #exponential #strict
- Exponential Lower Bounds for Restricted Monotone Circuits (LGV), pp. 110–117.
- ICALP-1983-ChandraFL #bound #constant #problem
- Lower Bounds for Constant Depth Circuits for Prefix Problems (AKC, SF, RJL), pp. 109–117.
- ICALP-1983-HambruschS #bound #graph #problem
- Lower Bounds for Solving Undirected Graph Problems on VLSI (SEH, JS), pp. 292–303.
- STOC-1982-PachlKR #algorithm #bound #distributed #proving
- A Technique for Proving Lower Bounds for Distributed Maximum-Finding Algorithms (JKP, EK, DR), pp. 378–382.
- ICALP-1982-Kalorkoti #bound
- A Lower Bound for the Formula Size of Rational Functions (KK), pp. 330–338.
- STOC-1981-Fich #bound #detection #problem
- Lower Bounds for the Cycle Detection Problem (FEF), pp. 96–105.
- STOC-1981-LiptonS #bound
- Lower Bounds for VLSI (RJL, RS), pp. 300–307.
- ICALP-1981-Snir #bound #proving
- Proving Lower Bounds for Linar Decision Trees (MS), pp. 305–315.
- STOC-1979-LengauerT #bound #trade-off
- Upper and Lower Bounds on Time-Space Tradeoffs (TL, RET), pp. 262–277.
- STOC-1979-Sipser #automaton #bound
- Lower Bounds on the Size of Sweeping Automata (MS), pp. 360–364.
- STOC-1977-YaoAR #bound #problem
- An Ω(n² log n) Lower Bound to the Shortest Paths Problem (ACCY, DA, RLR), pp. 11–17.
- ICALP-1976-AltM #bound #complexity #recognition
- Lower Bounds for the Space Complexity of Context-Free Recognition (HA, KM), pp. 338–354.
- STOC-1975-FischerMP #bound
- Lower Bounds on the Size of Boolean Formulas: Preliminary Report (MJF, ARM, MP), pp. 37–44.
- STOC-1975-Paul #bound #combinator #complexity
- A 2.5 n-lower Bound on the Combinatorial Complexity of Boolean Functions (WJP), pp. 27–36.
- STOC-1975-Valiant #bound #complexity #on the
- On Non-linear Lower Bounds in Computational Complexity (LGV), pp. 45–53.
- STOC-1974-Kedem #bound #multi
- Combining Dimensionality and Rate of Growth Arguments for Establishing Lower Bounds on the Number of Multiplications (ZMK), pp. 334–341.
- STOC-1974-Kung #algorithm #bound #evaluation #parallel
- New Algorithms and Lower Bounds for the Parallel Evaluation of Certain Rational Expressions (HTK), pp. 323–333.