Testing Equivalence of Polynomials under Shifts (Englisch)
- Neue Suche nach: Dvir, Z.
- Neue Suche nach: de Oliveira, R.M.
- Neue Suche nach: Shpilka, A.
- Neue Suche nach: Dvir, Z.
- Neue Suche nach: de Oliveira, R.M.
- Neue Suche nach: Shpilka, A.
- Neue Suche nach: Esparza, Javier
In:
Automata, languages and programming: 41st international colloquium, ICALP 2014,Part I
8572
;
417-428
;
2014
-
ISBN:
-
ISSN:
- Aufsatz (Konferenz) / Print
-
Titel:Testing Equivalence of Polynomials under Shifts
-
Beteiligte:
-
Kongress:International colloquium; 41st, Automata, languages and programming: 41st international colloquium, ICALP 2014,Part I ; 2014 ; Copenhagen
-
Erschienen in:Automata, languages and programming: 41st international colloquium, ICALP 2014,Part I , 8572 ; 417-428LECTURE NOTES IN COMPUTER SCIENCE , 8572 ; 417-428
-
Verlag:
- Neue Suche nach: Springer
-
Erscheinungsort:Heidelberg
-
Erscheinungsdatum:01.01.2014
-
Format / Umfang:12 pages
-
Anmerkungen:Includes bibliographical references and index. Also issued online. Part I of II See NUMB 8573 for Part II
-
ISBN:
-
ISSN:
-
Medientyp:Aufsatz (Konferenz)
-
Format:Print
-
Sprache:Englisch
-
Schlagwörter:
-
Datenquelle:
© Metadata Copyright the British Library Board and other contributors. All rights reserved.
Inhaltsverzeichnis Konferenzband
Die Inhaltsverzeichnisse werden automatisch erzeugt und basieren auf den im Index des TIB-Portals verfügbaren Einzelnachweisen der enthaltenen Beiträge. Die Anzeige der Inhaltsverzeichnisse kann daher unvollständig oder lückenhaft sein.
- 1
-
Sporadic Solutions to Zero-One Exclusion TasksGafni, E. / Herlihy, M. et al. | 2014
- 1
-
Symmetric Groups and Quotient Complexity of Boolean OperationsBell, J. / Brzozowski, J. / Moreira, N. / Reis, R. et al. | 2014
- 11
-
Verifying and Synthesizing Software with Recursive Functions (Invited Contribution)Kuncak, V. et al. | 2014
- 13
-
Handling Infinitely Branching WSTSBlondin, M. / Finkel, A. / McKenzie, P. et al. | 2014
- 26
-
Transducers with Origin InformationBojanczyk, M. et al. | 2014
- 26
-
Weak ParityAaronson, S. / Ambainis, A. / Balodis, K. / Bavarian, M. et al. | 2014
- 39
-
Consequences of Faster Alignment of SequencesAbboud, A. / Williams, V.V. / Weimann, O. et al. | 2014
- 50
-
On the Decidability of MSO+U on Infinite TreesBojanczyk, M. / Gogacz, T. / Michalewski, H. / Skrzypczak, M. et al. | 2014
- 52
-
Distance Labels with Optimal Local StretchAbraham, I. / Chechik, S. et al. | 2014
- 62
-
A Coalgebraic Foundation for Coinductive Union TypesBonsangue, M. / Rot, J. / Ancona, D. / de Boer, F. / Rutten, J. et al. | 2014
- 64
-
Time-Expanded PackingsAdjiashvili, D. / Bosio, S. / Weismantel, R. / Zenklusen, R. et al. | 2014
- 74
-
Turing Degrees of Limit Sets of Cellular AutomataBorello, A. / Cervelle, J. / Vanier, P. et al. | 2014
- 86
-
On the Complexity of Temporal-Logic Path CheckingBundala, D. / Ouaknine, J. et al. | 2014
- 89
-
The Tropical Shadow-Vertex Algorithm Solves Mean Payoff Games in Polynomial Time on AverageAllamigeon, X. / Benchimol, P. / Gaubert, S. et al. | 2014
- 98
-
Parameterised LinearisabilityCerone, A. / Gotsman, A. / Yang, H. et al. | 2014
- 101
-
Tighter Relations between Sensitivity and Other Complexity MeasuresAmbainis, A. / Bavarian, M. / Gao, Y. / Mao, J. / Sun, X. / Zuo, S. et al. | 2014
- 114
-
On Hardness of Jumbled IndexingAmir, A. / Chan, T.M. / Lewenstein, M. / Lewenstein, N. et al. | 2014
- 122
-
The Complexity of Ergodic Mean-payoff GamesChatterjee, K. / Ibsen-Jensen, R. et al. | 2014
- 126
-
Morphing Planar Graph Drawings OptimallyAngelini, P. / Da Lozzo, G. / Di Battista, G. / Frati, F. / Patrignani, M. / Roselli, V. et al. | 2014
- 134
-
Toward a Structure Theory of Regular Infinitary Trace LanguagesChaturvedi, N. et al. | 2014
- 138
-
Incremental Algorithm for Maintaining DFS Tree for Undirected GraphsBaswana, S. / Khan, S. et al. | 2014
- 146
-
Unary Pushdown Automata and Straight-Line ProgramsChistikov, D. / Majumdar, R. et al. | 2014
- 150
-
On the Role of Shared Randomness in Simultaneous CommunicationBavarian, M. / Gavinsky, D. / Ito, T. et al. | 2014
- 158
-
Robustness against Power is PSpace-completeDerevenetc, E. / Meyer, R. et al. | 2014
- 163
-
Short PCPs with Projection QueriesBen-Sasson, E. / Viola, E. et al. | 2014
- 171
-
A Nivat Theorem for Weighted Timed Automata and Weighted Relative Distance LogicDroste, M. / Perevoshchikov, V. et al. | 2014
- 174
-
Star Partitions of Perfect Graphsvan Bevern, R. / Bredereck, R. / Bulteau, L. / Chen, J. / Froese, V. / Niedermeier, R. / Woeginger, G.J. et al. | 2014
- 183
-
Computability in Anonymous Networks: Revocable vs. Irrecovable OutputsEmek, Y. / Seidel, J. / Wattenhofer, R. et al. | 2014
- 186
-
Coordination Mechanisms for Selfish Routing over Time on a TreeBhattacharya, S. / Kulkarni, J. / Mirrokni, V. et al. | 2014
- 196
-
Coalgebraic Weak Bisimulation from Recursive Equations over MonadsGoncharov, S. / Pattinson, D. et al. | 2014
- 198
-
On Area-Optimal Planar Graph DrawingsBiedl, T. et al. | 2014
- 208
-
Piecewise Boolean Algebras and Their DomainsHeunen, C. et al. | 2014
- 211
-
Shortest Two Disjoint Paths in Polynomial TimeBjorklund, A. / Husfeldt, T. et al. | 2014
- 223
-
Listing TrianglesBjorklund, A. / Pagh, R. / Williams, V.V. / Zwick, U. et al. | 2014
- 232
-
Bisimulation Equivalence of First-Order GrammarsJancar, P. et al. | 2014
- 235
-
On DNF Approximators for Monotone Boolean FunctionsBlais, E. / Hastad, J. / Servedio, R.A. / Tan, L.-Y. et al. | 2014
- 244
-
Context Unification is in PSPACEJez, A. et al. | 2014
- 247
-
Internal DLA: Efficient Simulation of a Physical Growth Model (Extended Abstract)Bringmann, K. / Kuhn, F. / Panagiotou, K. / Peter, U. / Thomas, H. et al. | 2014
- 259
-
Lower Bounds for Approximate LDCsBriet, J. / Dvir, Z. / Hu, G. / Saraf, S. et al. | 2014
- 271
-
Holographic Algorithms Beyond MatchgatesCai, J.-Y. / Guo, H. / Williams, T. et al. | 2014
- 280
-
Kleene Algebra with EquationsKozen, D. / Mamouras, K. et al. | 2014
- 283
-
Testing Probability Distributions Underlying Aggregated DataCanonne, C. / Rubinfeld, R. et al. | 2014
- 293
-
All-Instances Termination of Chase is UndecidableGogacz, T. / Marcinkowski, J. et al. | 2014
- 296
-
Parallel Repetition of Entangled Games with Exponential Decay via the Superposed Information CostChailloux, A. / Scarpa, G. et al. | 2014
- 305
-
Non-uniform Polytime Computation in the Infinitary Affine Lambda-CalculusMazza, D. et al. | 2014
- 308
-
The Bose-Hubbard Model is QMA-completeChilds, A.M. / Gosset, D. / Webb, Z. et al. | 2014
- 318
-
On the Positivity Problem for Simple Linear Recurrence SequencesOuaknine, J. / Worrell, J. et al. | 2014
- 320
-
Characterization of Binary Constraint System GamesCleve, R. / Mittal, R. et al. | 2014
- 330
-
Ultimate Positivity is Decidable for Simple Linear Recurrence SequencesOuaknine, J. / Worrell, J. et al. | 2014
- 332
-
Fast Algorithms for Constructing Maximum Entropy Summary TreesCole, R. / Karloff, H. et al. | 2014
- 342
-
Going Higher in the First-Order Quantifier Alternation Hierarchy on WordsPlace, T. / Zeitoun, M. et al. | 2014
- 344
-
Thorp Shuffling, Butterflies, and Non-markovian CouplingsCzumaj, A. / Vocking, B. et al. | 2014
- 356
-
Dynamic Complexity of Directed Reachability and Other ProblemsDatta, S. / Hesse, W. / Kulkarni, R. et al. | 2014
- 363
-
Branching Bisimilarity Checking for PRSYin, Q. / Fu, Y. / He, C. / Huang, M. / Tao, X. et al. | 2014
- 368
-
One Tile to Rule Them All: Simulating Any Tile Assembly System with a Single Universal TileDemaine, E.D. / Demaine, M.L. / Fekete, S.P. / Patitz, M.J. / Schweller, R.T. / Winslow, A. / Woods, D. et al. | 2014
- 375
-
Labeling Schemes for Bounded Degree GraphsAdjiashvili, D. / Rotbart, N. et al. | 2014
- 380
-
Canadians Should Travel RandomlyDemaine, E.D. / Huang, Y. / Liao, C.-S. / Sadakane, K. et al. | 2014
- 387
-
Bounded-Angle Spanning Tree: Modeling Networks with Angular ConstraintsAschner, R. / Katz, M.J. et al. | 2014
- 399
-
Distributed Computing on Core-Periphery Networks: Axiom-Based DesignAvin, C. / Borokhovich, M. / Lotker, Z. / Peleg, D. et al. | 2014
- 405
-
Parameterized Complexity of Bandwidth on TreesDregi, M.S. / Lokshtanov, D. et al. | 2014
- 411
-
Fault-Tolerant Rendezvous in NetworksChalopin, J. / Dieudonne, Y. / Labourel, A. / Pelc, A. et al. | 2014
- 417
-
Testing Equivalence of Polynomials under ShiftsDvir, Z. / de Oliveira, R.M. / Shpilka, A. et al. | 2014
- 423
-
Data Delivery by Energy-Constrained Mobile Agents on a LineChalopin, J. / Jacob, R. / Mihalak, M. / Widmayer, P. et al. | 2014
- 429
-
Optimal Analysis of Best Fit Bin PackingDosa, G. / Sgall, J. et al. | 2014
- 435
-
The Power of Two Choices in Distributed VotingCooper, C. / Elsasser, R. / Radzik, T. et al. | 2014
- 442
-
Light SpannersElkin, M. / Neiman, O. / Solomon, S. et al. | 2014
- 459
-
Facility Location in Evolving MetricsEisenstat, D. / Mathieu, C. / Schabanel, N. et al. | 2014
- 465
-
Online Stochastic Reordering Buffer SchedulingEsfandiari, H. / Hajiaghayi, M. / Khani, M.R. / Liaghat, V. / Mahini, H. / Racke, H. et al. | 2014
- 471
-
Solving the ANTS Problem with Asynchronous Finite State MachinesEmek, Y. / Langner, T. / Uitto, J. / Wattenhofer, R. et al. | 2014
- 477
-
Demand Queries with PreprocessingFeige, U. / Jozeph, S. et al. | 2014
- 483
-
Near-Optimal Distributed Approximation of Minimum-Weight Connected Dominating SetGhaffari, M. et al. | 2014
- 489
-
Algorithmic Aspects of Regular Graph Covers with Applications to Planar GraphsFiala, J. / Klavik, P. / Kratochvil, J. / Nedela, R. et al. | 2014
- 495
-
Randomized Rumor Spreading in Dynamic GraphsGiakkoupis, G. / Sauerwald, T. / Stauffer, A. et al. | 2014
- 502
-
Public vs Private Coin in Bounded-Round InformationBraverman, M. / Garg, A. et al. | 2014
- 508
-
Online Independent Set Beyond the Worst-Case: Secretaries, Prophets, and PeriodsGobel, O. / Hoefer, M. / Kesselheim, T. / Schleiden, T. / Vocking, B. et al. | 2014
- 520
-
Optimal Competitiveness for Symmetric Rectilinear Steiner Arborescence and Related ProblemsKantor, E. / Kutten, S. et al. | 2014
- 525
-
Improved Submatrix Maximum Queries in Monge MatricesGawrychowski, P. / Mozes, S. / Weimann, O. et al. | 2014
- 532
-
Orienting Fully Dynamic Graphs with Worst-Case Time BoundsKopelowitz, T. / Krauthgamer, R. / Porat, E. / Solomon, S. et al. | 2014
- 538
-
For-All Sparse Recovery in Near-Optimal TimeGilbert, A.C. / Li, Y. / Porat, E. / Strauss, M.J. et al. | 2014
- 544
-
Does Adding More Agents Make a Difference? A Case Study of Cover Time for the Rotor-RouterKosowski, A. / Pajak, D. et al. | 2014
- 551
-
Families with Infants: A General Approach to Solve Hard Partition ProblemsGolovnev, A. / Kulikov, A.S. / Mihajlin, I. et al. | 2014
- 556
-
The Melbourne Shuffle: Improving Oblivious Storage in the CloudOhrimenko, O. / Goodrich, M.T. / Tamassia, R. / Upfal, E. et al. | 2014
- 563
-
Changing Bases: Multistage Optimization for Matroids and MatchingsGupta, A. / Talwar, K. / Wieder, U. et al. | 2014
- 568
-
Sending Secrets Swiftly: Approximation Algorithms for Generalized Multicast ProblemsNikzad, A. / Ravi, R. et al. | 2014
- 576
-
Near-Optimal Online Algorithms for Prize-Collecting Steiner ProblemsHajiaghayi, M. / Liaghat, V. / Panigrahi, D. et al. | 2014
- 588
-
Nearly Linear-Time Model-Based Compressive SensingHegde, C. / Indyk, P. / Schmidt, L. et al. | 2014
- 600
-
Breaking the PPSZ Barrier for Unique 3-SATHertli, T. et al. | 2014
- 612
-
Privately Solving Linear ProgramsHsu, J. / Roth, A. / Roughgarden, T. / Ullman, J. et al. | 2014
- 637
-
Why Some Heaps Support Constant-Amortized-Time Decrease-Key Operations, and Others Do NotIacono, J. / Ozkan, O. et al. | 2014
- 650
-
Partial Garbling Schemes and Their ApplicationsIshai, Y. / Wee, H. et al. | 2014
- 663
-
On the Complexity of Trial and Error for Constraint Satisfaction ProblemsIvanyos, G. / Kulkarni, R. / Qiao, Y. / Santha, M. / Sundaram, A. et al. | 2014
- 676
-
Information Theoretical CryptogenographyJakobsen, S.K. et al. | 2014
- 713
-
Distance Oracles for Time-Dependent NetworksKontogiannis, S. / Zaroliagis, C. et al. | 2014
- 726
-
Efficient Indexing of Necklaces and Irreducible Polynomials over Finite FieldsKopparty, S. / Kumar, M. / Saks, M. et al. | 2014
- 738
-
Coloring Relatives of Interval Overlap Graphs via On-line GamesKrawczyk, T. / Walczak, B. et al. | 2014
- 751
-
Superpolynomial Lower Bounds for General Homogeneous Depth 4 Arithmetic CircuitsKumar, M. / Saraf, S. et al. | 2014
- 763
-
Testing Forest-Isomorphism in the Adjacency List ModelKusumoto, M. / Yoshida, Y. et al. | 2014
- 775
-
Parameterized Approximation Schemes Using Graph WidthsLampis, M. et al. | 2014
- 787
-
FPTAS for Weighted Fibonacci Gates and Its ApplicationsLu, P. / Wang, M. / Zhang, C. et al. | 2014
- 800
-
Parameterized Algorithms to Preserve ConnectivityBasavaraju, M. / Fomin, F.V. / Golovach, P. / Misra, P. / Ramanujan, M.S. / Saurabh, S. et al. | 2014
- 812
-
Nonuniform Graph Partitioning with Unrelated WeightsMakarychev, K. / Makarychev, Y. et al. | 2014
- 823
-
Precedence-Constrained Scheduling of Malleable Jobs with PreemptionMakarychev, K. / Panigrahi, D. et al. | 2014
- 835
-
Unbounded Entanglement Can Be Needed to Achieve the Optimal Success ProbabilityMancinska, L. / Vidick, T. et al. | 2014
- 847
-
QCSP on Semicomplete DigraphsDapic, P. / Markovic, P. / Martin, B. et al. | 2014
- 871
-
Determining Majority in Networks with Local Interactions and Very Small Local MemoryMertzios, G.B. / Nikoletseas, S.E. / Raptopoulos, C.L. / Spirakis, P.G. et al. | 2014
- 883
-
Lower Bounds for Oblivious Subspace EmbeddingsNelson, J. / Nguyen, H.L. et al. | 2014
- 907
-
Secure Computation Using Leaky TokensPrabhakaran, M. / Sahai, A. / Wadia, A. et al. | 2014
- 919
-
An Improved Interactive Streaming Algorithm for the Distinct Elements ProblemKlauck, H. / Prakash, V. et al. | 2014
- 943
-
Pseudorandom Graphs in Data StructuresReingold, O. / Rothblum, R.D. / Wieder, U. et al. | 2014
- 955
-
Sampling-Based Proofs of Almost-Periodicity Results and Algorithmic ApplicationsBen-Sasson, E. / Ron-Zewi, N. / Tulsiani, M. / Wolf, J. et al. | 2014
- 967
-
The Mondshein SequenceSchmidt, J.M. et al. | 2014
- 991
-
Close to Uniform Prime Number Generation with Fewer Random BitsFouque, P.-A. / Tibouchi, M. et al. | 2014
- 1003
-
Optimal Strong Parallel Repetition for Projection Games on Low Threshold Rank GraphsTulsiani, M. / Wright, J. / Zhou, Y. et al. | 2014
- 1015
-
Sparser Random 3-SAT Refutation Algorithms and the Interpolation Problem (Extended Abstract)Tzameret, I. et al. | 2014
- 1027
-
On Learning, Lower Bounds and (un)Keeping PromisesVolkovich, I. et al. | 2014
- 1039
-
Certificates in Data StructuresWang, Y. / Yin, Y. et al. | 2014
- 1051
-
Optimal Query Complexity for Estimating the Trace of a MatrixWimmer, K. / Wu, Y. / Zhang, P. et al. | 2014
- 1063
-
Faster Separators for Shallow Minor-Free Graphs via Dynamic Approximate Distance OraclesWulff-Nilsen, C. et al. | 2014
- 1075
-
Spatial Mixing of Coloring Random GraphsYin, Y. et al. | 2014