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.